“资源分配型” 动态规划总结

“资源分配型” 动态规划的总结与例题，还包含背包问题的理解。

前言
#

资源分配型动态规划一般题目会表达为：在序列化结构（数组、字符串等）中，用有限的操作资源完成特定操作，使最终收益最大或代价最小。

注意，这种题目也可能使用搜索，而使用动态规划的关键是：

当前是否使用资源会影响后续状态
是否有重复子问题

此外，从时间复杂度也能看出该选择此类动态规划，一般该类问题复杂度为: $$O(m n)$$ 其中 n 是数组长度，m 是资源数量。

通常模板
#

状态定义
#

dp[i][j] = 处理前 i 个元素时，使用 j 次资源后的最优解（最大收益/最小代价）

状态转移
#

决策 1：不使用资源

dp[i][j] = dp[i-1][j] + 当前代价（如白砖 + 1，股票未交易保持状态等）
决策 2：使用资源

if j >= 1: dp[i][j] = max/min(dp[i - L][j - 1], …) # L 为资源覆盖长度

初始化
#

基准状态

dp[0][0] = 初始代价/收益（如第一个元素是否被覆盖）
资源越界处理

for i in range(L): # 比如前 L 个元素使用一次资源的情况

用地毯覆盖后的最少白色砖块
#

2209. 用地毯覆盖后的最少白色砖块

原题
#

给你一个下标从 0 开始的二进制字符串 floor，它表示地板上砖块的颜色。

floor[i] = '0' 表示地板上第 i 块砖块的颜色是黑色
floor[i] = '1' 表示地板上第 i 块砖块的颜色是白色

同时给你 numCarpets 和 carpetLen。你有 numCarpets 条黑色的地毯，每一条黑色的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余白色砖块的数目最小。地毯相互之间可以覆盖。

请你返回没被覆盖的白色砖块的最少数目。

示例：

输入：floor = "10110101", numCarpets = 2, carpetLen = 2
输出：2
如右侧所示：░█▒▒█▒█░，灰色是被地毯覆盖

思路与题解
#

其中地砖为进度轴、地毯为资源轴。

设置地砖为 i，地毯为 j，则状态定义为：前 i 个地砖用 j 个地毯后的最小白砖数量。

状态转移方程见下面代码的注释：

# 动态规划，有限资源分配问题
# 如果想到状态定义就不算难：前 i 个地砖用 j 个地毯后的最小白砖数量
class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        n = len(floor)
        dp = [[inf] * (numCarpets + 1) for _ in range(n)]
        dp[0][0] = int(floor[0])
        for i in range(carpetLen): # 前 carpetLen 个白格被盖住
            dp[i][1] = 0
        for i in range(n):
            for j in range(numCarpets + 1):
                if floor[i] == '1': # 如果是白格，最小格子数加一
                    dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
                if floor[i] == '0': # 黑格不加
                    dp[i][j] = min(dp[i][j], dp[i - 1][j])
                if i - carpetLen >= 0 and j - 1 >= 0: # 贪心，尽量让地毯不重复铺
                    dp[i][j] = min(dp[i - carpetLen][j - 1], dp[i][j])

        # 如果最后地毯没用完，说明一定可以使得白砖全部被铺满
        return dp[n - 1][numCarpets] if dp[n - 1][numCarpets] != inf else 0

买卖股票的最佳时机 IV
#

188. 买卖股票的最佳时机 IV

原题
#

给你一个整数数组 prices 和一个整数 k，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（即，你必须在再次购买之前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2, 4, 1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4 - 2 = 2。

示例 2：

输入：k = 2, prices = [3, 2, 6, 5, 0, 3]
输出：7
解释：
在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出，这笔交易所能获得利润 = 6 - 2 = 4。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出，这笔交易所能获得利润 = 3 - 0 = 3

提示：

0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

思路与题解
#

此题用 记忆化搜索 要简单一些，其原理和上面的动态规划相同。

同样是 i 表示进度轴，j 表示 资源数量。

根据题目要求，要多一个 当前是否持有股票 的状态。

# 记忆化搜索或 DP 
# 此题记忆化搜索好想一点
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        @cache
        # i 是数组下标即当前最后统计的元素，记忆化搜索从后向前容易
        # j 是当前剩余的买卖次数
        # hold 标记当前是否存有股票
        # 如果转成 DP 需要三维
        def dfs(i : int, j : int, hold : bool) -> int:
            if (j == -1): 
                # 次数都用完了 直接返回
                # 此处用 -inf 是防止 -inf + price[i] 超过 0 的情况
                return -inf
            if (i == -1):
                # 返回 -1 代表不可能递归到第一个数时还持有股票
                # 实际上存的是第 0 天的两个状态
                return -inf if hold else 0
            if hold:
                # 两种可能 前为刚买的 后为之前就存有的，j 只需要在购买时维护
                return max(dfs(i - 1, j - 1, False) - prices[i], dfs(i - 1, j, True))
            else:
                # 两种可能 前为刚卖的 后为之前就没有
                return max(dfs(i - 1, j, True) + prices[i], dfs(i - 1, j, False))
        return dfs(n - 1, k, False) # 最后一定是不持有股票

其他题目
#

410. 分割数组的最大值

状态定义是：数组中前 i 个数在当前切割成 j 个数组

此外，该题也需要使用前缀和来获取 o1 的区间求和。

背包问题
#

背包问题，也可以看作这种类型的动态规划。

一般而言分成 01背包 和 完全背包。

01背包：每个物品只能选一次。

完全背包：每个物品可以重复选。

两者状态定义为：前 i 个物品在容量为 j 的背包中的最大价值

状态转移方程分别为：（1为01背包、2为完全背包）

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
dp[i][j] = max(dp[i - 1][j], dp[i][j - weights[i - 1]] + values[i - 1])

两道零钱兑换
#

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：`coins = [1, 2, 5]`, `amount = 11`  
输出：`3`  
解释：11 = 5 + 5 + 1

题解：

此题是经典的完全背包问题。

但由于其要得到的是最少硬币数量，因此可以看作每个硬币的价值相同（其中的价值不是 amount，而是上面状态转移方程中的 value[]）。

因此可以节省一个维度，代码如下：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # DP下标是当前金额 内容是硬币数量
        dp = [inf] * (amount + 1)
        dp[0] = 0
        for coin in coins:
            for i in range(1, amount + 1):
                if i < coin:
                    continue
                dp[i] = min(dp[i], dp[i - coin] + 1)

        return dp[amount] if dp[amount] != inf else -1

518. 零钱兑换 Ⅱ

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

题解：

此题要的是凑出最大零钱的种类，那么为什么不能直接用Ⅰ的思路？
Ⅰ的遍历顺序无关：因为求的是最小值，无论是先遍历硬币还是金额，最终都能得到最少硬币数（例如 coins = [1,2,5]，amount=5，无论顺序如何，最少硬币数都是1）。
Ⅱ的遍历顺序关键：组合数的统计必须避免重复计数（例如 2+1+1 和 1+2+1 视为同一种组合）。
Ⅱ先遍历硬币，后遍历金额的遍历顺序，可以看作通过固定硬币的遍历顺序，保证组合的唯一性。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] += (dp[i - coin])
        return dp[amount]