购买水果需要的最少金币数

100133. 购买水果需要的最少金币数

你在一个水果超市里，货架上摆满了玲琅满目的奇珍异果。

给你一个下标从 1 开始的数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。

水果超市有如下促销活动：

如果你花费 price[i] 购买了水果 i ，那么接下来的 i 个水果你都可以免费获得。

注意，即使你可以免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以便能免费获得接下来的 j 个水果。

请你返回获得所有水果所需要的最少金币数。

示例 1：

输入：prices = [3,1,2]
输出：4
解释：你可以按如下方法获得所有水果：
- 花 3 个金币购买水果 1 ，然后免费获得水果 2 。
- 花 1 个金币购买水果 2 ，然后免费获得水果 3 。
- 免费获得水果 3 。
注意，虽然你可以免费获得水果 2 ，但你还是花 1 个金币去购买它，因为这样的总花费最少。
购买所有水果需要最少花费 4 个金币。

示例 2：

输入：prices = [1,10,1,1]
输出：2
解释：你可以按如下方法获得所有水果：
- 花 1 个金币购买水果 1 ，然后免费获得水果 2 。
- 免费获得水果 2 。
- 花 1 个金币购买水果 3 ，然后免费获得水果 4 。
- 免费获得水果 4 。
购买所有水果需要最少花费 2 个金币。

提示：

1 <= prices.length <= 1000
1 <= prices[i] <= 10⁵

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minimumCoins(vector<int>& prices) { } };

python3 解法, 执行用时: 172 ms, 内存消耗: 18.5 MB, 提交时间: 2023-11-26 16:34:41

class Solution:
    # dp
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        @cache
        def dfs(i: int) -> int:
            if i * 2 >= n:
                return prices[i - 1]  # i 从 1 开始
            return min(dfs(j) for j in range(i + 1, i * 2 + 2)) + prices[i - 1]
        return dfs(1)

    # 递推
    def minimumCoins2(self, prices: List[int]) -> int:
        n = len(prices)
        for i in range((n + 1) // 2 - 1, 0, -1):
            prices[i - 1] += min(prices[i: i * 2 + 1])
        return prices[0]

java 解法, 执行用时: 3 ms, 内存消耗: 42.2 MB, 提交时间: 2023-11-26 16:35:24

class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length;
        for (int i = (n + 1) / 2 - 1; i > 0; i--) {
            int mn = Integer.MAX_VALUE;
            for (int j = i; j <= i * 2; j++) {
                mn = Math.min(mn, prices[j]);
            }
            prices[i - 1] += mn;
        }
        return prices[0];
    }

    // dp
    public int minimumCoins2(int[] prices) {
        int n = prices.length;
        int[] memo = new int[(n + 1) / 2];
        return dfs(1, prices, memo);
    }

    private int dfs(int i, int[] prices, int[] memo) {
        if (i * 2 >= prices.length) {
            return prices[i - 1]; // i 从 1 开始
        }
        if (memo[i] != 0) { // 之前算过
            return memo[i];
        }
        int res = Integer.MAX_VALUE;
        for (int j = i + 1; j <= i * 2 + 1; j++) {
            res = Math.min(res, dfs(j, prices, memo));
        }
        return memo[i] = res + prices[i - 1]; // 记忆化
    }
}

cpp 解法, 执行用时: 32 ms, 内存消耗: 19.9 MB, 提交时间: 2023-11-26 16:36:08

class Solution {
public:
    int minimumCoins(vector<int> &prices) {
        int n = prices.size();
        vector<int> memo((n + 1) / 2);
        function<int(int)> dfs = [&](int i) -> int {
            if (i * 2 >= n) {
                return prices[i - 1]; // i 从 1 开始
            }
            int &res = memo[i]; // 注意这里是引用
            if (res) { // 之前算过
                return res;
            }
            res = INT_MAX;
            for (int j = i + 1; j <= i * 2 + 1; j++) {
                res = min(res, dfs(j));
            }
            res += prices[i - 1];
            return res;
        };
        return dfs(1);
    }

    // 递推
    int minimumCoins2(vector<int> &prices) {
        int n = prices.size();
        for (int i = (n + 1) / 2 - 1; i > 0; i--) {
            prices[i - 1] += *min_element(prices.begin() + i, prices.begin() + i * 2 + 1);
        }
        return prices[0];
    }
};

golang 解法, 执行用时: 4 ms, 内存消耗: 2.9 MB, 提交时间: 2023-11-26 16:36:42

func minimumCoins(prices []int) int {
	n := len(prices)
	for i := (n+1)/2 - 1; i > 0; i-- {
		prices[i-1] += slices.Min(prices[i : i*2+1])
	}
	return prices[0]
}

// dp
func minimumCoins2(prices []int) int {
	n := len(prices)
	memo := make([]int, (n+1)/2)
	var dfs func(int) int
	dfs = func(i int) int {
		if i*2 >= n {
			return prices[i-1] // i 从 1 开始
		}
		p := &memo[i]
		if *p != 0 { // 之前算过
			return *p
		}
		res := math.MaxInt
		for j := i + 1; j <= i*2+1; j++ {
			res = min(res, dfs(j))
		}
		res += prices[i-1]
		*p = res // 记忆化
		return res
	}
	return dfs(1)
}

上一题

下一题

详情