摘要: 先找到重复子问题，然后通过状态转移方程描述最优子结构

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，今天我们来看一个动态规划的问题，拿到问题之后，首先手推一两步，看能不能得到规模更小的子问题，如果不能，则考虑是不是加了一些额外信息之后可以构成子问题。先有了子问题，然后在考虑状态转移方程的过程中自然就找到了最优子结构。

本题的难点还在于后续优化，第一个点是可以通过给已有的状态维度赋予额外信息，来代替增加一个状态维度来引入额外信息；第二个点是通过状态转移方程的推导过程发现其中有单调队列可以高效维护的操作。

本题是一个思路逐步递进，且算法点没有超纲的难得好题，推荐花些时间研究一下。

题目

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

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

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

• 如果你花费 prices[i] 购买了下标为 i 的水果，那么你可以免费获得下标范围在 [i + 1, i + i] 的水果。

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

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

提示：

1
2

1 <= prices.length <= 1000
1 <= prices[i] <= 1e5

示例 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, n]$ 这些元素需要决定是否购买，购买元素 $i$ 需要付出 $p[i]$，得到 $[i, \min(2i, n)]$ 这些元素。（$i$ 从 1 开始计）

我们要做的是通过决定 $[1, n]$ 这些元素购买哪些，来得到 $[1, n]$ 中的全部元素，使得总费用最小。

我们按照 $i=1,2,\cdot,n$ 依次考虑第 $i$ 个元素是否购买，看看会有什么发现。

首先考虑第一个元素 $i=1$，由于这一元素无法通过购买更早的元素免费获得，只能购买，付出 $p[1]$，同时得到了 $[1, 2]$ 这两个元素。

后续我们需要考虑 $[2, n]$ 这些元素购买哪些，这似乎是一个子问题，但是稍有不同，就是这里 $2$ 这个元素已经通过购买 $1$ 免费获得了，因此在考虑 $2$ 是否购买的时候，就是可买可不买，我们需要分别来看。

• 如果买 $2$，则付出 $p[2]$，得到 $[2, 4]$，后续需要继续考虑 $[3, n]$ 中要购买哪些来获得所有元素，并且其中只有 $[5, n]$ 的元素尚未获得。
• 如果不买 $2$，则付出与得到均无变化，后续依然需要继续考虑 $[3, n]$ 中要购买哪些来获得所有元素，并且其中所有的 $[3, n]$ 这些元素都尚未获得。

这里我们就发现，如果通过记录哪些元素尚未决定购买，同时哪些元素尚未获得，就可以构成需要重复解决的子问题。

具体地，就是记 $dp[i][j]$ 表示需要考虑 $[i, n]$ 这些元素购买哪些来获得全部 $i, n$ 的元素，且其中 $[j, n]$ 这些元素尚未获得。如此定义的话，我们要求的答案就是 $dp[1][1]$。当 $j > n$ 时，所有元素均已获得，这是边界情况，此时的答案为 0。

下面是状态转移方程：

该状态转移方程描述了 $dp[i][j]$ 这个状态表示对应的最优子结构。

至此，最优子结构、重复子问题齐了，对应的状态表示很明确，状态转移方程很清晰，状态推导的过程就是线性推导，边界条件也不复杂，直接走一遍这个动态规划即可。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

from functools import lru_cache

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)

        @lru_cache(maxsize=int(1e7))
        def solve(i: int, j: int) -> int:
            if j > n:
                return 0
            
            ans = prices[i - 1] + solve(i + 1, max(j, i * 2 + 1))
            
            if i < j:
                ans = min(ans, solve(i + 1, j))
            return ans

        return solve(1, 1)

优化

优化1：优化状态表示

考虑到了第几个元素作为阶段，即定义 $dp[i]$ 表示考虑 $[i, n]$ 这些元素购买哪些元素，使得可以获得 $[i, n]$ 的所有元素同时费用最小，这里 $i$ 就是阶段。

在前面的分析中，我们知道，仅以 $i$ 这一阶段信息是不构成最优子结构的，需要额外信息。前面我们的做法是引入了另一状态维度 $j$ 来表示额外信息，即 $i$ 之前购买的元素中已经免费获得的元素信息。综合下来得到状态表示 $dp[i][j]$，含义是考虑 $[i, n]$ 这些元素购买哪些来获得全部 $i, n$ 的元素，且其中 $[j, n]$ 这些元素尚未获得。

这里我们还可以考虑另一种引入额外信息的思路，也就是直接在阶段的维度 $i$ 上赋予额外信息，即 $dp[i]$ 在原有的含义上再增加上 $i$ 这个元素必选的要求。这样的话，由于第一个元素始终是必选的，$dp[1]$ 依然是答案。接下来考虑状态转移的过程。

当我们推导 $dp[i]$ 的答案时，考虑的问题是 $[i, n]$ 这些元素均视为没有在之前免费获得过，这样 $i$ 必选，在这样的情况下，获得 $[i, n]$ 所有元素最少需要多少金币。

此时当我们选了 $i$，付出 $p[i]$，获得了 $[i, 2i]$ 这些元素，接下来就要考虑下一个购买的是哪个。直观上，下一个直接买 $2i+1$ 是可以的，这样考虑的子问题自然就是 $dp[2i+1]$，对应的候选答案为 $p[i] + dp[2i + 1]$，其含义是花费 $p[i]$ 选择 $i$，然后免费获得的 $[i+1, 2i]$ 就都不去购买了，然后再在必选 $2i+1$ 的情况下去获得 $[2i+1, n]$ 这些元素，最少支付 $dp[2i+1]$。

当然，$[i+1, 2i]$ 这些由于购买 $i$ 而免费获得的元素，都是可以选择去买的。前面的 $p[i] + dp[2i+1]$ 这一候选解仅考虑了 $[i+1, 2i]$ 这些元素都不买的情况。如果下一个购买的是 $j$，这里 $i+1 \leq j \leq 2i$，此时虽然 $j$ 已经免费获得了，但我们可以将其视为没有免费获得，这样就进入了子问题 $dp[j]$，对应的候选答案就为 $p[i] + dp[j]$。

综上，状态转移方程为：

由状态转移方程我们发现状态的推导过程完全就是从右向左线性推导的，因此可以按照 $i = n-1,n-2,\cdots,1$ 通过递推的方式依次推导即可。

如果 $2i \geq n$，则花费 $p[i]$ 购买 $i$ 后，后续就不用再买了，因此 $dp[i] = p[i]$ 即可，这是边界条件。

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [-1] * (n + 1)
        for i in range(n, 0, -1):
            dp[i] = prices[i - 1]
            if i * 2 >= n:
                continue
            mx = dp[i + 1]
            for j in range(i + 1, min(i * 2 + 2, n + 1)):
                mx = min(mx, dp[j])
            dp[i] += mx
        return dp[1]

优化2：单调队列优化DP

观察状态转移方程：

其中 $\min\limits_{i+1 \leq j \leq 2i+1} dp[j]$ 这部分是要在 $j \in [l, r]$ 中找到 $dp[j]$ 的最小值，其中 $l=i+1, r=2i+1$。当 $i$ 从右往左推导的时候，$l$ 与 $r$ 也向左移动，这正是滑动窗口最小值问题，我们知道通过单调队列，可以做到每次最小值的查询都是摊销 $O(1)$ 的。参考文章：

• 单调队列优化DP
• 单调队列

当 dp[i] 计算完成后，在算 dp[i-1] 以及更左的状态时，dp[i] 是有可能作为滑窗最小值的查询结果的，将 $i$ 压入单调队列。此时，由于 $i$ 的压入将导致队列中的一些下标变得无效，需要弹出，有两部分：

• 一是此时单调队列下标都是大于 $i$ 的，其中对应的 $dp$ 值如果大于等于 $dp[i]$，那么在推导 $dp[i-1]$ 以及更左的状态时，单调队列中由于 $dp[i]$ 的存在，它们无论如何都不可能是后续的滑窗最小值的查询结果。
• 二是当 $i$ 压入后，后续的查询中最大可能的右端点为 $2(i-1)+1=2i-1$，因此单调队列中大于 $2i-1$ 的可以弹出了。

综上，在从右到左推导状态 $i$ 时，维护的是一个下标从小到大，对应的 $dp$ 值从大到小的队列 deq，在计算 $dp[i]$ 时，队尾对应的就是滑动窗口最小值的结果，用其更新答案即可，由于单调队列的特性，这步优化为了摊销 $O(1)$。

然后再推导下一状态 $dp[i-1]$ 之前，先更新 deq，首先将所有 $dp$ 值大于等于 $dp[i]$ 的下标从队头弹出，然后所有大于 $2i-1$ 的下标从队尾弹出，然后将 $i$ 从队头压入。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [-1] * (n + 1)
        deq = deque()
        for i in range(n, 0, -1):
            dp[i] = prices[i - 1]
            if i * 2 < n:
                dp[i] += dp[deq[-1]]
            while len(deq) > 0 and dp[deq[0]] >= dp[i]:
                deq.popleft()
            while len(deq) > 0 and deq[-1] > i * 2 - 1:
                deq.pop()
            deq.appendleft(i)
        return dp[1]