动态规划实战：完全背包、零钱兑换与排列组合

一维优化

第一步：观察二维公式的秘密

dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])

仔细观察等号右边的两个状态：

1. dp[i - 1][j]：这是上一层（上一行）的正上方的数据。
2. dp[i][j - weight[i]]：这是当前层（同一行）左边的数据。

这意味着，我们在推导当前格子时，只需要用到正上方和同一行左边的数据，更早的历史数据其实已经没用了！

第二步：压缩成一维数组

既然每次只需要用到上一行和当前行的数据，我们为什么不直接用一个一维数组 dp[j] 来记录呢？

假设我们把二维数组'拍扁'成一行 dp[j]：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

• 等号右边的第一个 dp[j]：因为还没被更新，它其实就相当于二维数组里的 dp[i - 1][j]（继承自上一次遍历的结果）。
• 等号右边的 dp[j - weight[i]]：重点来了！如果我们让容量 j 从小到大遍历（从左往右填表），当我们要计算当前的 dp[j] 时，它左边的 dp[j - weight[i]] 一定已经在当前这一轮被更新过了。这就完美等同于二维里的 dp[i][j - weight[i]]！

第三步：对比 0-1 背包，理解遍历顺序（核心考点）

这里是无数人栽跟头的地方，请务必留意：

• 0-1 背包：每个物品只能放一次。为了防止当前物品被重复放入，一维数组必须从大到小（从右往左）倒序遍历背包容量。这样在计算后面的大容量时，前面小容量的状态还是上一轮的旧数据（没放过该物品）。
• 完全背包：每个物品可以放无限次。为了允许当前物品被重复放入，一维数组必须从小到大（从左往右）正序遍历背包容量。这样在计算后面的大容量时，前面小容量的状态已经是放过当前物品的新数据了，这就实现了'放了还能再放'的效果！

第四步：代码

def knapsack_1d(n, bag_weight, weight, value):
    # 初始化一个长度为 bag_weight + 1 的一维数组，全部填 0
    dp = [0] * (bag_weight + 1)
    # 先遍历物品
    for i in range(n):
        # 再遍历背包容量（完全背包：从小到大正序遍历！）
        # 注意：直接从 weight[i] 开始遍历即可，因为比它小的容量根本放不下当前物品，无需更新
        for j in range(weight[i], bag_weight + 1):
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    # 数组的最后一个元素就是最大价值
    return dp[bag_weight]

# 测试数据
n, bag_weight = 3, 4
weight = [1, 3, 4]
value = [15, 20, 30]
print(knapsack_1d(n, bag_weight, weight, value)) # 输出 60

518. 零钱兑换 II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 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

示例 2:

• 输入：amount = 3, coins = [2]
• 输出：0
• 解释：只用面额 2 的硬币不能凑成总金额 3。

示例 3:

• 输入：amount = 10, coins = [10]
• 输出：1

注意，你可以假设：

• 0 <= amount (总金额) <= 5000
• 1 <= coin (硬币面额) <= 5000
• 硬币种类不超过 500 种
• 结果符合 32 位符号整数

第一步 确定 dp 数组以及下标的含义

dp[i][j]：使用 下标为 [0, i] 的 coins[i] 能够凑满 j（包括 j）这么大容量的包，有 dp[i][j] 种组合方法。

第二步 确定递推公式

在装满背包有几种方法中详解讲解了装满背包有几种方法，二维 DP 数组的递推公式：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]

所以本题递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i]]，区别依然是 dp[i - 1][j - nums[i]] 和 dp[i][j - nums[i]]

第三步 dp 数组如何初始化

那么最上行 dp[0][j] 如何初始化呢？

dp[0][j] 的含义：用「物品 0」（即 coins[0]） 装满 背包容量为 j 的背包，有几种组合方法。（如果看不懂 dp 数组的含义，建议先学习目标和）

如果 j 可以整除 物品 0，那么装满背包就有 1 种组合方法。

初始化代码：

for (int j = 0; j <= bagSize; j++) {
    if (j % coins[0] == 0) dp[0][j] = 1;
}

最左列如何初始化呢？

dp[i][0] 的含义：用物品 i（即 coins[i]） 装满容量为 0 的背包 有几种组合方法。

都有一种方法，即不装。

所以 dp[i][0] 都初始化为 1

第四步 确定遍历顺序

二维无所谓先后

二维 dp 递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]

压缩成一维：dp[j] += dp[j - coins[i]]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0]*(amount + 1)
        dp[0] = 1
        # 遍历物品
        for i in range(len(coins)):
            # 遍历背包
            for j in range(coins[i], amount + 1):
                dp[j] += dp[j - coins[i]]
        return dp[amount]

377. 组合总和 IV

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

• nums = [1, 2, 3]
• target = 4

所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

第一步 确定 dp 数组以及下标的含义

dp[i]: 凑成目标正整数为 i 的排列个数为 dp[i]

第二步 确定递推公式

dp[i]（考虑 nums[j]）可以由 dp[i - nums[j]]（不考虑 nums[j]） 推导出来。

因为只要得到 nums[j]，排列个数 dp[i - nums[j]]，就是 dp[i] 的一部分。

dp[i] += dp[i - nums[j]];

第三步 dp 数组如何初始化

因为递推公式 dp[i] += dp[i - nums[j]] 的缘故，dp[0] 要初始化为 1，这样递归其他 dp[i] 的时候才会有数值基础。

第四步 确定遍历顺序

个数可以不限使用，说明这是一个完全背包。

得到的集合是排列，说明需要考虑元素之间的顺序。

本题要求的是排列，那么这个 for 循环嵌套的顺序可以有说法了。

在零钱兑换 II 中就已经讲过了。

如果求组合数就是外层 for 循环遍历物品，内层 for 遍历背包。

如果求排列数就是外层 for 遍历背包，内层 for 循环遍历物品。

如果把遍历 nums（物品）放在外循环，遍历 target 的作为内循环的话，举一个例子：计算 dp[4] 的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为 nums 遍历放在外层，3 只能出现在 1 后面！

所以本题遍历顺序最终遍历顺序：target（背包）放在外循环，将 nums（物品）放在内循环，内循环从前到后遍历。

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        # 创建动态规划数组，用于存储组合总数
        dp[0] = 1
        # 初始化背包容量为 0 时的组合总数为 1
        for i in range(1, target + 1):
            # 遍历背包容量
            for j in nums:
                # 遍历物品列表
                if i >= j:
                    # 当背包容量大于等于当前物品重量时
                    dp[i] += dp[i - j]
                    # 更新组合总数
        return dp[-1]
        # 返回背包容量为 target 时的组合总数

70. 爬楼梯（进阶）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多 m (1 <= m < n) 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

输入描述：输入共一行，包含两个正整数，分别表示 n, m

输出描述：输出一个整数，表示爬到楼顶的方法数。

输入示例：3 2

输出示例：3

提示：

当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。

此时你有三种方法可以爬到楼顶。

• 1 阶 + 1 阶 + 1 阶段
• 1 阶 + 2 阶
• 2 阶 + 1 阶

第一步 确定 dp 数组以及下标的含义

dp[i]：爬到有 i 个台阶的楼顶，有 dp[i] 种方法。

第二步 确定递推公式

dp[i] 有几种来源，dp[i - 1]，dp[i - 2]，dp[i - 3] 等等，即：dp[i - j]

那么递推公式为：dp[i] += dp[i - j]

第三步 dp 数组如何初始化

既然递归公式是 dp[i] += dp[i - j]，那么 dp[0] 一定为 1，dp[0] 是递归中一切数值的基础所在，如果 dp[0] 是 0 的话，其他数值都是 0 了。

下标非 0 的 dp[i] 初始化为 0，因为 dp[i] 是靠 dp[i-j] 累计上来的，dp[i] 本身为 0 这样才不会影响结果

第四步 确定遍历顺序

这是背包里求排列问题，即：1、2 步 和 2、1 步都是上三个台阶，但是这两种方法不一样！

所以需将 target 放在外循环，将 nums 放在内循环。

每一步可以走多次，这是完全背包，内循环需要从前向后遍历。

def climbing_stairs(n,m):
    dp = [0]*(n+1) # 背包总容量
    dp[0] = 1 # 排列题，注意循环顺序，背包在外物品在内
    for j in range(1,n+1):
        for i in range(1,m+1):
            if j>=i:
                dp[j] += dp[j-i] # 这里 i 就是重量而非 index
    return dp[n]

if __name__ == '__main__':
    n,m = list(map(int,input().split(' ')))
    print(climbing_stairs(n,m))