2944. 购买水果需要的最少金币数(1709)

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

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

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

  • 如果你花费 price[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] <= 10^5

动态规划（递推）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length, res = (int)1e9;
        // 如果是从左到右递推，那么就要定义f[i]: 购买第i个水果及左边的水果，所花费的最少金币数，这样很难构建递推关系
        // 这题需要从右往左递推，定义f[i]: 购买第i个水果及右边的水果，花费的最少金币数
        // f[i] = prices[i-1] + min(f[i+1:r])
        int f[] = new int[n+1];
        for (int i = n; i > 0; i--) {
            f[i] = prices[i-1];
            int r = i*2+1;  // 当前免费获得水果的窗口的右边界 + 1
            if (r > n) continue;
            int min = (int)1e9;
            for (int j = i+1; j <= r; j++) {
                min = Math.min(min, f[j]);
            }
            f[i] += min;
        }
        return f[1];
    }
}

动态规划(递推) + 单调栈优化(获取窗口最小值)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length, res = (int)1e9;
        // 如果是从左到右递推，那么就要定义f[i]: 购买第i个水果及左边的水果，所花费的最少金币数，这样很难构建递推关系
        // 这题需要从右往左递推，定义f[i]: 购买第i个水果及右边的水果，花费的最少金币数
        // f[i] = prices[i-1] + min(f[i+1:r])
        int f[] = new int[n+1];
        // 优化：用单调栈维护窗口的最小值
        Deque<Integer> dq = new LinkedList<>();
        for (int i = n; i > 0; i--) {
            f[i] = prices[i-1];
            int r = i*2+1;  // 当前免费获得水果的窗口的右边界 + 1
            if (r <= n) {
                while (!dq.isEmpty() && r < dq.peekLast()) {  // 删除超过当前窗口范围的索引
                    dq.pollLast();
                }
                f[i] += f[dq.peekLast()];  // 栈顶存储窗口最小值
            }
            while (!dq.isEmpty() && f[i] < f[dq.peek()]) {  // 递增栈
                dq.pop();
            }
            dq.push(i);
        }
        return f[1];
    }
}