每日一题20250124-LC2944

题目信息

掌握程度: 🌟

给你一个下标从 1 开始的整数数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。
水果超市有如下促销活动：
如果你花费 prices[i] 购买了下标为 i 的水果，那么你可以免费获得下标范围在 [i + 1, i + i] 的水果。注意，即使你可以免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以获得它的奖励。
请你返回获得所有水果所需要的最少金币数。
示例 1：
输入：prices = [3,1,2]
输出：4
解释：
用 prices[0] = 3 个金币购买第 1 个水果，你可以免费获得第 2 个水果。用 prices[1] = 1 个金币购买第 2 个水果，你可以免费获得第 3 个水果。免费获得第 3 个水果。请注意，即使您可以免费获得第 2 个水果作为购买第 1 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。
示例 2：
输入：prices = [1,10,1,1]
输出：2
解释：
用 prices[0] = 1 个金币购买第 1 个水果，你可以免费获得第 2 个水果。免费获得第 2 个水果。用 prices[2] = 1 个金币购买第 3 个水果，你可以免费获得第 4 个水果。免费获得第 4 个水果。示例 3：
输入：prices = [26,18,6,12,49,7,45,45]
输出：39
解释：
用 prices[0] = 26 个金币购买第 1 个水果，你可以免费获得第 2 个水果。免费获得第 2 个水果。用 prices[2] = 6 个金币购买第 3 个水果，你可以免费获得第 4，5，6（接下来的三个）水果。免费获得第 4 个水果。免费获得第 5 个水果。用 prices[5] = 7 个金币购买第 6 个水果，你可以免费获得第 7 和第 8 个水果。免费获得第 7 个水果。免费获得第 8 个水果。请注意，即使您可以免费获得第 6 个水果作为购买第 3 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。
提示：
1 <= prices.length <= 1000 1 <= prices[i] <= 105

解题思路

先看看 case1 ，如果我们购买了 0 ，这个时候有两个选择

免费获取 1 ，我们只能购买 2 , 总花费是 5
不免费获取 1 ，我们免费获取 2，总花费是 4

所以我们选择第二种方案，这种方案代价最低

我们需要考虑的是，对于 dp[i] 我们定义其含义为购买了 i 时，获取从 dp[i+1] 到 dp[2i] 的最小花费

计算 dp[i] ，我们需要计算 j from [i+1] to [2i] 中的最小花费，在加上 price[i]

\[ \text{dfs}(i) = \text{prices}[i] + \min_{j=i+1}^{2i+1} \text{dfs}(j) \]

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    public int minimumCoins(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]; // 记忆化
    }

每日一题20250124-LC2944

题目信息

解题思路

代码实现

相关文章：