动态规划中的完全背包问题及其变体。首先介绍了完全背包的二维和一维解法，重点分析了遍历顺序（正序）与 01 背包的区别。随后通过零钱兑换 II、组合总和 IV 及爬楼梯进阶三个经典例题，深入探讨了求组合数与排列数的区别，以及循环嵌套顺序对结果的影响。文章提供了完整的 Python 代码实现与状态转移方程推导，帮助读者掌握动态规划的核心逻辑。
有 N 件物品和一个最多能背重量为 W 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i]。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和 01 背包问题唯一不同的地方就是，每种物品有无限件。
例子：
背包最大重量为 4，物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品 0 | 1 | 15 |
| 物品 1 |
| 3 |
| 20 |
| 物品 2 | 4 | 30 |
每件商品都有无限个！
问背包能背的物品最大价值是多少？
dp[i][j] 表示从下标为 [0-i] 的物品，每个物品可以取无限次，放进容量为 j 的背包，价值总和最大是多少。
递推公式：dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
（注意，完全背包二维 dp 数组 和 01 背包二维 dp 数组 递推公式的区别，01 背包中是 dp[i - 1][j - weight[i]] + value[i])）
首先从 dp[i][j] 的定义出发，如果背包容量 j 为 0 的话，即 dp[i][0]，无论是选取哪些物品，背包价值总和一定为 0。
状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]); 可以看出有一个方向 i 是由 i-1 推导出来，那么 i 为 0 的时候就一定要初始化。
dp[0][j]，即：存放编号 0 的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0] 的时候，dp[0][j] 应该是 0，因为背包容量比编号 0 的物品重量还小。
当 j >= weight[0] 时，dp[0][j] 如果能放下 weight[0] 的话，就一直装，每一种物品有无限个。
二维 dp：
既可以先遍历物品再遍历背包，也可以先遍历背包再遍历物品
以本篇举例数据为例，填满了 dp 二维数组如图：
因为 物品 0 的性价比是最高的，而且 在完全背包中，每一类物品都有无限个，所以有无限个物品 0，既然物品 0 性价比最高，当然是优先放物品 0。
def knapsack(n, bag_weight, weight, value):
dp = [[0] * (bag_weight + 1) for _ in range(n)]
# 初始化
for j in range(weight[0], bag_weight + 1):
dp[0][j] = dp[0][j - weight[0]] + value[0]
# 动态规划
for i in range(1, n):
for j in range(bag_weight + 1):
if j < weight[i]:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])
return dp[n - 1][bag_weight]
# 输入
n, bag_weight = map(int, input().split())
weight = []
value = []
for _ in range(n):
w, v = map(int, input().split())
weight.append(w)
value.append(v)
# 输出结果
print(knapsack(n, bag_weight, weight, value))
dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])
仔细观察等号右边的两个状态：
这意味着，我们在推导当前格子时，只需要用到正上方和同一行左边的数据，更早的历史数据其实已经没用了！
既然每次只需要用到上一行和当前行的数据，我们为什么不直接用一个一维数组 dp[j] 来记录呢？
假设我们把二维数组'拍扁'成一行 dp[j]：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
这里是无数人栽跟头的地方，请务必留意：
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
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
解释：有四种方式可以凑成总金额：
示例 2:
示例 3:
注意，你可以假设：
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[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]
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
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[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 时的组合总数
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多 m (1 <= m < n) 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
输入描述：输入共一行，包含两个正整数，分别表示 n, m
输出描述：输出一个整数，表示爬到楼顶的方法数。
输入示例：3 2
输出示例：3
提示：
当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。
此时你有三种方法可以爬到楼顶。
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[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))
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online