如果求组合数就是外层for循环遍历物品内层for遍历背包。如果求排列数就是外层for遍历背包内层for循环遍历物品。为什么标准二维 DP天然就是组合数没有排列数最常见的二维定义dp[i][j] 用前 i 种硬币凑出金额 j 的方案数一维DP也就是对待一个 ji 循环一次加一次把所有i循环一遍才是dp【j】的值。比如dp【3】dp3药跟着i循环很多次但都是dp【3】i1时 dp【3】dp[2]022i2时dp【3】2dp【1】3,i3,dp33dp[0]4,dp【3】就这样循环在i到头时才是真正的dp【j】的值。为什么遍历顺序能控制顺序核心一句话外层循环决定 什么东西只出现一次内层循环决定 什么东西反复尝试。情况一外层物品内层背包 → 组合数plaintextfor 每个硬币: ← 外层物品一个一个来 for 每个金额: ← 内层对每个金额决定用不用这个硬币 dp[j] dp[j - coin]模拟过程coins [1, 2], amount 3第 1 轮只考虑硬币 1表格金额dp[j]方案01空111211131111第 2 轮加入硬币 2表格金额dp[j]方案01空111不变1 221 dp[0] 211、231 dp[1] 2111、12关键观察当处理硬币 2 时dp[j - 2]里存的是只用硬币 1凑出 j-2 的方案数。所以新增的方案一定是 前面都是 1最后加一个 2——2 永远出现在 1 后面不会出现 21。就像你按面值从小到大决定 每种硬币用几个每个硬币只决策一次天然不会有顺序问题。情况二外层背包内层物品 → 排列数plaintextfor 每个金额: ← 外层金额一个一个来 for 每个硬币: ← 内层对每个金额尝试所有硬币 dp[j] dp[j - coin]模拟过程coins [1, 2], amount 3j 1硬币 1dp [1] dp [0] → dp [1] 1方案1硬币 21 2跳过j 2硬币 1dp [2] dp [1] → dp [2] 1方案11硬币 2dp [2] dp [0] → dp [2] 2新增2j 3硬币 1dp [3] dp [2] → dp [3] 2方案111、12硬币 2dp [3] dp [1] → dp [3] 3新增21关键观察当算金额 3、用硬币 2 时dp[3 - 2] dp[1]而 dp [1] 里存的是 凑 1 元的所有排列也就是 [1]。所以新增的方案是 最后一步放 2前面随便怎么凑 1—— 这就产生了 21。就像你在想 凑 j 元最后一枚硬币放什么每次都可以选任意硬币不同的最后一枚自然产生不同的排列。场景重置爬楼梯问题假设你要爬上第i级台阶你每次可以跨nums数组里的步数比如nums[1,2,3]你可以跨 1 步、2 步或 3 步。定义dp[i]爬到第i级台阶一共有多少种不同的爬法顺序不同算不同。 大脑思考“最后一步”的直觉当你要爬到第i级台阶时你只需要想一个问题“我最后一步是怎么跨上来的”如果最后一步跨了1步那么我之前必须在第i-1级台阶。爬到i-1级有dp[i-1]种方法。如果最后一步跨了2步那么我之前必须在第i-2级台阶。爬到i-2级有dp[i-2]种方法。如果最后一步跨了3步那么我之前必须在第i-3级台阶。爬到i-3级有dp[i-3]种方法。所以总方法数就是dp[i] dp[i-1] dp[i-2] dp[i-3]。一句话总结表格遍历顺序相当于在想结果外层物品内层背包每种硬币用几个组合顺序无关外层背包内层物品最后一步放哪个物品排列顺序有关