1. 项目概述从“选数”到“方案数”的动态规划实战最近在整理算法笔记翻到了“数字组合”这道经典题目。表面上看它就是一个给定一堆数字和一个目标和问有多少种不同的选取方式能让选出的数字之和正好等于目标值。很多新手朋友第一反应就是回溯暴力枚举所有子集这思路没错但一旦数字规模上去比如给几十个数字时间复杂度立刻爆炸。这道题的精妙之处或者说它之所以被归为经典是因为它完美地诠释了如何将一个“组合计数”问题转化为一个“01背包”问题并且核心诉求从“求最大价值”变成了“求方案总数”。这不仅仅是换个状态定义那么简单其背后的状态转移逻辑和初始化技巧是理解动态规划中“计数类”问题的绝佳入口。我们常说的01背包标准模型是有一个容量为V的背包和N件物品每件物品体积为v[i]价值为w[i]每件物品只能选0次或1次。目标是求能装入背包的物品的最大总价值。状态f[j]通常表示“对于前i件物品背包容量为j时能获得的最大价值”。而“数字组合”问题实际上是把每个数字看作一个物品其“体积”和“价值”都是数字本身的值背包容量就是目标和T。但我们的目标不是求最大价值因为如果数字都是正整数尽可能装满时最大价值就是T本身这个信息没用而是要求“恰好装满容量为T的背包有多少种不同的物品组合方式”。这要求我们对状态定义和转移方程进行根本性的重构。理解这个转化是解决一系列衍生问题如“目标和”、“零钱兑换II”的关键。接下来我会彻底拆解这个转化过程从最朴素的回溯思路引出问题再到01背包的动态规划解法并重点剖析求方案数时的状态转移方程、初始化细节以及那些容易踩坑的边界条件。无论你是正在备战算法面试还是想深化对动态规划的理解相信这篇详尽的拆解都能给你带来收获。2. 问题定义与核心思路剖析2.1 问题场景与抽象建模让我们先形式化地定义一下“数字组合”问题输入一个正整数目标值target以及一个正整数数组nums可能包含重复数字但通常在此类问题中组合不考虑顺序且每个数字最多使用一次。输出从nums中选取若干个数每个数最多选一次使得它们的和恰好等于target的不同选取方式的数目。例如nums [1, 2, 3],target 4。那么组合方式有[1,3]和[2,2]不对2只有一个所以[2,2]不合法。[4]数组里没有4。[1,1,2]1只能用一次。所以实际上只有[1,3]这一种组合。如果nums [1, 2, 3, 4]target4那么组合有[4]和[1,3]两种。如何抽象成背包问题物品数组nums中的每一个数字对应一件物品。物品体积与价值每件物品的“体积”v[i]就是数字本身的值同时在这个问题里物品的“价值”w[i]也是这个数字的值。但请注意在方案计数中“价值”这个概念并不直接参与状态转移的计算它被“方案数”取代了。背包容量目标值target就是背包的总容量V。物品限制每个数字只能选一次这就是01背包的“01”特性。背包状态我们不再关心“最大价值”而是关心“方案数”。因此我们需要一个新的状态数组dp[j]。注意这里有一个非常重要的点题目通常暗示或明示每个数字是唯一的且只能使用一次。如果数字可以无限次使用那就变成了“完全背包”的计数问题状态转移方程会有所不同。我们当前聚焦于01背包场景。2.2 从回溯到动态规划的思路演进面对这个问题最直接的思路是回溯法DFS。我们可以遍历每个数字选择“取”或者“不取”当路径上的数字和等于target时就记录一种方案。其递归树是指数级的时间复杂度为O(2^N)。当N较大时比如超过30这个算法就不可行了。动态规划的核心思想是用空间换时间通过记录并复用子问题的解来避免重复计算。对于“数字组合”一个关键的观察是当我们考虑前i个数字要凑出总和j的方案数时这个结果可以由更小的子问题推导出来。具体来说对于第i个数字其值为num情况一不选择第i个数字。那么凑出总和j的方案数就等于只考虑前i-1个数字时凑出总和j的方案数。情况二选择第i个数字。那么前提是j num。选择了它之后我们需要用前i-1个数字去凑出剩下的总和j - num。因此方案数就等于只考虑前i-1个数字时凑出总和j - num的方案数。由于“不选”和“选”是互斥的两种决策且它们都能独立地贡献方案数因此总的方案数就是这两种情况方案数之和。这就导出了我们的状态转移方程。2.3 状态定义与转移方程确立我们定义动态规划的状态dp[i][j]表示考虑前i个物品数字恰好装满容量为j的背包的方案总数。根据上面的分析我们可以得到状态转移方程dp[i][j] dp[i-1][j] dp[i-1][j - nums[i-1]]当j nums[i-1]时dp[i][j] dp[i-1][j]当j nums[i-1]时这里nums[i-1]对应第i个物品的价值/体积因为数组下标从0开始。为什么是“恰好装满”题目要求总和恰好等于target而不是“不超过”。这影响了初始化的方式。对于“恰好”类问题通常只有容量为0的背包有一种方案什么也不选即dp[0][0] 1。而其他容量j 0的背包在没有任何物品时是无法“恰好装满”的所以dp[0][j] 0。在实际编码中我们通常会使用空间优化的技巧。观察状态转移方程dp[i][j]只依赖于dp[i-1][j]和dp[i-1][j-num]即当前行只依赖于上一行。因此我们可以将二维数组压缩成一维数组但需要注意遍历顺序。定义一维状态dp[j]表示恰好装满容量为j的背包的方案总数。 状态转移方程变为dp[j] dp[j] dp[j - num]对于每个数字num需要逆序遍历j从target到num。这个方程可以这样理解新的dp[j]考虑当前数字后等于旧的dp[j]不考虑当前数字即不选它加上dp[j - num]选当前数字前提是之前能凑出j-num。逆序遍历是为了保证在计算dp[j]时dp[j - num]还是上一轮考虑前i-1个物品的状态避免当前轮次对同一个数字的重复使用这正是01背包一维优化的核心。3. 核心细节解析与初始化陷阱3.1 “恰好”与“不超过”的本质区别这是此类问题第一个容易混淆的点。我们对比一下两种状态定义dp[j]恰好装满容量j的方案数。初始化dp[0] 1表示容量为0的背包有一种方案什么都不装。对于j 0dp[j] 0因为没有任何物品时无法恰好装满任何正数容量的背包。最终答案dp[target]。dp[j]容量不超过j的方案数或最大价值问题中的常见定义。初始化dp[0...target] 0或根据价值初始化对于最大价值问题通常dp[0...target] 0。最终答案dp[target]可能包含了所有不超过target的方案而不是恰好等于。在计数问题中这通常不是我们想要的。对于“数字组合”问题我们必须使用“恰好装满”的定义。初始化dp[0]1是正确计数的基石。你可以这样理解当我们考虑第一个数字num时如果要凑出j num那么方案数应该是dp[num] dp[num] dp[0]。如果dp[0]不是1那么这个组合就无法被正确计数。3.2 一维DP的逆序遍历原理这是第二个关键细节也是01背包空间优化的精髓。为什么必须逆序从target遍历到num假设我们正序遍历j从num到target。考虑num 2。计算dp[2]dp[2] dp[2] dp[0]。假设初始dp[0]1,dp[2]0则更新后dp[2]1。这表示用数字2凑出容量2有一种方案。计算dp[4]dp[4] dp[4] dp[2]。注意此时的dp[2]已经是本轮更新后的值1。这意味着在计算dp[4]时我们使用的dp[2]是已经包含了当前数字2的方案数。那么dp[4] 0 1 1这个结果实际对应的方案是[2, 2]即数字2被使用了两次。这违背了01背包“每个物品最多用一次”的规则。逆序遍历可以避免这个问题计算dp[4]dp[4] dp[4] dp[2]。此时dp[2]还是上一轮未考虑当前数字2的值是0。所以dp[4] 0。计算dp[2]dp[2] dp[2] dp[0]。dp[0]1所以dp[2]1。 逆序保证了在计算dp[j]时dp[j - num]存储的是“未考虑当前物品”时的状态从而每个物品只会被计入一次。3.3 处理重复数字与组合去重题目中数组nums可能包含重复的数字例如[1, 2, 2, 5]。我们的动态规划方法会自动处理这种情况吗答案是取决于我们如何定义“不同方案”。在标准的“数字组合”问题中“不同方案”指的是选取的数字构成的集合不同与顺序无关。例如用[1, 2, 2, 5]凑target3。方案有[1,2]取第一个2和[1,2]取第二个2。这两个方案选取的数字集合都是{1, 2}在集合视角下是同一个方案。我们的动态规划方法无论是二维还是一维其本质是遍历物品数组元素。对于两个值相同的数字2它们被当作两个不同的物品来处理。因此上述算法会认为[1, nums[1]]和[1, nums[2]]是两种不同的方案从而输出2。但这通常不符合题目的要求题目一般要求计算不同的组合数而非排列数也不是考虑物品ID的选取数。那么如何得到题目通常要求的“组合数”呢关键在于遍历顺序。我们刚才的“物品遍历”是放在外层的。实际上为了得到“组合数”与物品顺序无关我们应该把**“背包容量”的循环放在外层物品的循环放在内层吗不恰恰相反。在经典的01背包计数问题中为了确保结果是“组合数”而非“排列数”我们必须把遍历物品数字的循环放在最外层**遍历背包容量的循环放在内层并且是逆序。这样做的原因是外层循环遍历物品相当于我们按顺序考虑每个物品是否加入。当我们固定了物品的考虑顺序对于同一个总和[物品A, 物品B]和[物品B, 物品A]这两种放入背包的顺序由于物品A总是在物品B之前被考虑所以只有“先考虑A再考虑B”这一种决策路径会被计算。这就保证了我们计算的是组合数而不是排列数。即使有两个相同的数字因为它们被视为不同的物品且被按顺序考虑所以由它们形成的、实质相同的集合仍然会被重复计算。要解决这个由重复元素导致的重复计数需要在遍历前对nums数组进行排序去重或者使用更复杂的状态定义记录使用某个数值的次数但这通常超出了基础01背包计数的范畴属于“有重复物品的背包”问题。在面试或笔试中如果出现重复数字务必与面试官澄清“不同方案”的定义。4. 完整代码实现与逐行分析下面我将给出基于一维DP的两种经典实现方式并附上详细的注释。我们假设问题定义是标准的计算恰好和为target的不同组合数将值相同的数字视为相同的元素即题目输入可能包含重复值但组合时认为数字值相同则不可区分这通常需要先对数组进行处理或题目保证无重复。4.1 实现一基础一维DP解法这种解法假设nums中的数字都是唯一的或者题目明确说明结果按数字组合计不考虑数字来源只考虑数值此时重复数字会导致重复组合需要预处理去重。def combinationSum4_01(nums, target): 使用一维DP数组解决01背包数字组合问题。 假设nums中数字唯一或已去重。 # 初始化dp数组dp[j]表示恰好凑成总和j的方案数 dp [0] * (target 1) # 基础情况凑成总和0的方案有一种即什么都不选 dp[0] 1 # 外层循环遍历每个数字物品 for num in nums: # 内层循环逆序遍历背包容量 # 从target遍历到num确保每个数字只被使用一次 for j in range(target, num - 1, -1): # 状态转移方程dp[j] dp[j] dp[j - num] # dp[j] (旧)不选当前数字num凑成j的方案数 # dp[j - num]选了当前数字num则剩余容量为j-num需要凑成j-num的方案数 dp[j] dp[j] dp[j - num] # 如果担心整数溢出可以在这里取模例如dp[j] (dp[j] dp[j - num]) % MOD # 最终答案就是恰好凑成target的方案数 return dp[target] # 示例 nums [1, 2, 3] target 4 print(combinationSum4_01(nums, target)) # 输出1 (只有[1,3])逐行解析dp [0] * (target 1)创建长度为target1的一维数组下标j代表要凑的总和。初始化为0。dp[0] 1这是动态规划的“种子”。凑出总和0的方案有且只有一种一个数都不选。这个初始化是“恰好装满”类问题的关键。for num in nums:外层循环遍历每一个数字。每个数字就是一个物品这个循环顺序保证了我们计算的是“组合数”。for j in range(target, num - 1, -1):内层循环逆序从target遍历到num。逆序是01背包一维优化的核心它确保了在计算dp[j]时dp[j - num]是上一轮未考虑当前数字num的状态从而每个数字只用一次。条件j num是显然的因为如果当前背包容量j连数字num都放不下那就不可能选择这个数字。dp[j] dp[j] dp[j - num]经典的状态转移。dp[j]在原值不选num的方案数基础上加上选了num的方案数dp[j - num]。return dp[target]循环结束后dp[target]存储的就是用所有数字恰好凑出target的总方案数。4.2 实现二处理可能存在的重复数字预处理去重如果题目要求将数值相同的数字视为相同的即[1,2,2]中两个2没有区别那么直接使用上面的代码对于nums [1,2,2],target3会得到错误答案2因为它区分了第一个2和第二个2。正确的答案应该是1只有[1,2]。为了得到符合通常理解的组合数我们需要在DP前对数组进行去重。但注意去重后每个数字的“数量”变成了1。然而原题可能允许重复数字但组合时认为数字相同则不可区分这本质上意味着输入数组中的重复数字是冗余信息。更严谨的做法是如果数字可重复且数量有限应使用“多重背包”的计数方法。这里我们假设题目本意是集合Set操作或者我们通过预处理来符合常见题意。def combinationSum4_01_unique(nums, target): 处理nums中可能包含重复数字的情况。 通过排序和跳过重复数字确保每个数值只被考虑一次。 这适用于“数字组合”问题中将相同数值视为同一元素的情况。 # 排序以便于跳过重复元素虽然不是必须但好习惯 nums.sort() dp [0] * (target 1) dp[0] 1 # 遍历去重后的数字 i 0 n len(nums) while i n: num nums[i] # 逆序更新DP for j in range(target, num - 1, -1): dp[j] dp[j] dp[j - num] # 跳过所有相同的数字避免重复计数 while i 1 n and nums[i 1] num: i 1 i 1 return dp[target] # 示例 nums [1, 2, 2, 3] target 4 # 组合应为[1,3] 和 [2,2]? 注意去重后nums有效为[1,2,3]所以[2,2]无法构成。 print(combinationSum4_01_unique(nums, target)) # 输出1 (只有[1,3]) # 如果希望计算[2,2]则需要用“多重背包”或“完全背包”如果2可用无限次。这个版本在遍历时跳过了连续相同的数字确保每个不同的数值只作为一件“物品”被处理一次。这符合“从一堆数字中选若干个数求和”的常见组合解释。但务必注意这与原始题目《数字组合》的输入定义可能略有差异实际做题时应以题目描述为准。5. 常见问题、调试技巧与扩展思考5.1 典型错误与排查清单在实现和调试01背包计数问题时以下几个错误非常常见初始化错误忘记将dp[0]初始化为1导致所有结果都为0。这是最常犯的错误之一。务必理解dp[0]1是组合计数问题的“空集”基础。遍历顺序错误内层循环顺序错误使用了正序for j in range(num, target1)导致每个数字被重复使用多次变成了完全背包。一定要逆序内外层循环颠倒如果错误地将容量遍历放在外层数字遍历放在内层在某些情况下计算的是“排列数”而不是“组合数”。对于标准的01背包计数数字物品遍历必须在外层。数组越界在内层循环中没有正确处理j - num的下标当j num时不应进入更新逻辑。我们的循环条件for j in range(target, num-1, -1)很好地避免了这个问题。整数溢出方案数可能非常大超过普通整型范围。如果题目要求取模一定要在每次加法操作后取模而不是最后才取模。例如dp[j] (dp[j] dp[j - num]) % MOD。对“恰好”与“不超过”理解偏差错误地将dp数组全部初始化为1或者将dp[0]之外的其他位置也初始化为1这通常对应的是“不超过容量j”的方案数初始化方式但即便如此dp[0]也应为1。仔细审题确认是“恰好等于”还是“不超过”。调试小技巧打印DP表对于小规模数据在每次外层循环处理一个数字后打印出整个dp数组。观察其变化是否符合预期。这是理解DP过程最直观的方法。手动模拟用纸笔跟踪一个简单例子如nums[1,2], target3的整个DP过程验证你的代码每一步的状态更新。边界测试target0应该返回1空集。nums为空数组除了target0返回1其他target0都应返回0。nums中所有数字都大于target结果应为0。5.2 从“方案数”到“具体方案”上述DP只给出了方案的数量。如果题目要求输出所有具体的组合方案而不仅仅是计数那么动态规划就不再是最优选择了因为DP擅长计数但存储所有具体方案的空间开销可能巨大是指数级的。这时回溯法DFS是更合适的选择。回溯可以构造出所有可能的组合并通过剪枝例如当前和超过target则返回来提高效率。虽然最坏时间复杂度仍是O(2^N)但对于需要枚举所有解的问题这是不可避免的。def combinationSum4_dfs(nums, target): 使用回溯法找出所有组合方案数字可重复使用这里假设不可重复使用。 注意此方法用于枚举所有解对于计数问题效率低于DP。 def backtrack(start, path, current_sum): if current_sum target: result.append(path[:]) # 找到一组解 return if current_sum target or start len(nums): return # 选择当前数字 path.append(nums[start]) backtrack(start 1, path, current_sum nums[start]) path.pop() # 不选择当前数字 backtrack(start 1, path, current_sum) nums.sort() # 排序有助于某些剪枝但不是必须 result [] backtrack(0, [], 0) return result nums [1, 2, 3] target 4 print(combinationSum4_dfs(nums, target)) # 输出[[1, 3]]5.3 相关变种问题与扩展理解了01背包求方案数的核心后你可以尝试解决一系列变种问题它们都是在此模型上的扩展494. 目标和给定一个整数数组nums和一个整数target向数组中的每个整数前添加或-然后串联成表达式求运算结果等于target的不同表达式数目。这可以转化为一个子集和问题背包问题。设所有添加的数字和为P添加-的数字和为N则有P - N target且P N sum(nums)。解方程得P (target sum(nums)) / 2。问题转化为在nums中找出若干个数使其和恰好等于P的方案数。这就是一个标准的01背包计数问题注意P必须为非负整数。518. 零钱兑换 II给定不同面额的硬币和一个总金额计算可以凑成总金额的硬币组合数。假设每种硬币数量无限。这不再是01背包而是完全背包的计数问题。核心区别在于内层循环的遍历顺序需要正序遍历jfromcointoamount因为同一硬币可以重复使用。涉及顺序的排列数如果题目问的是排列数即[1,2]和[2,1]算两种例如“377. 组合总和 Ⅳ”题目名是组合但实际求排列。那么就需要将背包容量的遍历放在外层物品的遍历放在内层并且内层循环为正序如果物品可无限次使用或另做处理。这颠倒了01背包求组合数的循环顺序。最后一点个人心得动态规划尤其是背包问题是算法学习的重难点。理解的关键不在于背模板而在于想清楚状态的定义以及状态之间是如何转移的。“数字组合”这个问题提供了一个绝佳的练习场让你深入理解“计数”型DP与“最值”型DP在状态转移上的微妙差异。多动手画DP表多思考为什么初始化是那样为什么遍历顺序要这样比刷十道题都管用。当你再遇到“恰好装满”、“方案总数”这些关键词时你会立刻意识到哦这又是那个熟悉的背包计数问题只是换了一件外衣而已。 1. 项目概述从“选数”到“方案数”的动态规划实战最近在整理算法笔记翻到了“数字组合”这道经典题目。表面上看它就是一个给定一堆数字和一个目标和问有多少种不同的选取方式能让选出的数字之和正好等于目标值。很多新手朋友第一反应就是回溯暴力枚举所有子集这思路没错但一旦数字规模上去比如给几十个数字时间复杂度立刻爆炸。这道题的精妙之处或者说它之所以被归为经典是因为它完美地诠释了如何将一个“组合计数”问题转化为一个“01背包”问题并且核心诉求从“求最大价值”变成了“求方案总数”。这不仅仅是换个状态定义那么简单其背后的状态转移逻辑和初始化技巧是理解动态规划中“计数类”问题的绝佳入口。我们常说的01背包标准模型是有一个容量为V的背包和N件物品每件物品体积为v[i]价值为w[i]每件物品只能选0次或1次。目标是求能装入背包的物品的最大总价值。状态f[j]通常表示“对于前i件物品背包容量为j时能获得的最大价值”。而“数字组合”问题实际上是把每个数字看作一个物品其“体积”和“价值”都是数字本身的值背包容量就是目标和T。但我们的目标不是求最大价值因为如果数字都是正整数尽可能装满时最大价值就是T本身这个信息没用而是要求“恰好装满容量为T的背包有多少种不同的物品组合方式”。这要求我们对状态定义和转移方程进行根本性的重构。理解这个转化是解决一系列衍生问题如“目标和”、“零钱兑换II”的关键。接下来我会彻底拆解这个转化过程从最朴素的回溯思路引出问题再到01背包的动态规划解法并重点剖析求方案数时的状态转移方程、初始化细节以及那些容易踩坑的边界条件。无论你是正在备战算法面试还是想深化对动态规划的理解相信这篇详尽的拆解都能给你带来收获。2. 问题定义与核心思路剖析2.1 问题场景与抽象建模让我们先形式化地定义一下“数字组合”问题输入一个正整数目标值target以及一个正整数数组nums可能包含重复数字但通常在此类问题中组合不考虑顺序且每个数字最多使用一次。输出从nums中选取若干个数每个数最多选一次使得它们的和恰好等于target的不同选取方式的数目。例如nums [1, 2, 3],target 4。那么组合方式有[1,3]和[2,2]不对2只有一个所以[2,2]不合法。[4]数组里没有4。[1,1,2]1只能用一次。所以实际上只有[1,3]这一种组合。如果nums [1, 2, 3, 4]target4那么组合有[4]和[1,3]两种。如何抽象成背包问题物品数组nums中的每一个数字对应一件物品。物品体积与价值每件物品的“体积”v[i]就是数字本身的值同时在这个问题里物品的“价值”w[i]也是这个数字的值。但请注意在方案计数中“价值”这个概念并不直接参与状态转移的计算它被“方案数”取代了。背包容量目标值target就是背包的总容量V。物品限制每个数字只能选一次这就是01背包的“01”特性。背包状态我们不再关心“最大价值”而是关心“方案数”。因此我们需要一个新的状态数组dp[j]。注意这里有一个非常重要的点题目通常暗示或明示每个数字是唯一的且只能使用一次。如果数字可以无限次使用那就变成了“完全背包”的计数问题状态转移方程会有所不同。我们当前聚焦于01背包场景。2.2 从回溯到动态规划的思路演进面对这个问题最直接的思路是回溯法DFS。我们可以遍历每个数字选择“取”或者“不取”当路径上的数字和等于target时就记录一种方案。其递归树是指数级的时间复杂度为O(2^N)。当N较大时比如超过30这个算法就不可行了。动态规划的核心思想是用空间换时间通过记录并复用子问题的解来避免重复计算。对于“数字组合”一个关键的观察是当我们考虑前i个数字要凑出总和j的方案数时这个结果可以由更小的子问题推导出来。具体来说对于第i个数字其值为num情况一不选择第i个数字。那么凑出总和j的方案数就等于只考虑前i-1个数字时凑出总和j的方案数。情况二选择第i个数字。那么前提是j num。选择了它之后我们需要用前i-1个数字去凑出剩下的总和j - num。因此方案数就等于只考虑前i-1个数字时凑出总和j - num的方案数。由于“不选”和“选”是互斥的两种决策且它们都能独立地贡献方案数因此总的方案数就是这两种情况方案数之和。这就导出了我们的状态转移方程。2.3 状态定义与转移方程确立我们定义动态规划的状态dp[i][j]表示考虑前i个物品数字恰好装满容量为j的背包的方案总数。根据上面的分析我们可以得到状态转移方程dp[i][j] dp[i-1][j] dp[i-1][j - nums[i-1]]当j nums[i-1]时dp[i][j] dp[i-1][j]当j nums[i-1]时这里nums[i-1]对应第i个物品的价值/体积因为数组下标从0开始。为什么是“恰好装满”题目要求总和恰好等于target而不是“不超过”。这影响了初始化的方式。对于“恰好”类问题通常只有容量为0的背包有一种方案什么也不选即dp[0][0] 1。而其他容量j 0的背包在没有任何物品时是无法“恰好装满”的所以dp[0][j] 0。在实际编码中我们通常会使用空间优化的技巧。观察状态转移方程dp[i][j]只依赖于dp[i-1][j]和dp[i-1][j-num]即当前行只依赖于上一行。因此我们可以将二维数组压缩成一维数组但需要注意遍历顺序。定义一维状态dp[j]表示恰好装满容量为j的背包的方案总数。 状态转移方程变为dp[j] dp[j] dp[j - num]对于每个数字num需要逆序遍历j从target到num。这个方程可以这样理解新的dp[j]考虑当前数字后等于旧的dp[j]不考虑当前数字即不选它加上dp[j - num]选当前数字前提是之前能凑出j-num。逆序遍历是为了保证在计算dp[j]时dp[j - num]还是上一轮考虑前i-1个物品的状态避免当前轮次对同一个数字的重复使用这正是01背包一维优化的核心。3. 核心细节解析与初始化陷阱3.1 “恰好”与“不超过”的本质区别这是此类问题第一个容易混淆的点。我们对比一下两种状态定义dp[j]恰好装满容量j的方案数。初始化dp[0] 1表示容量为0的背包有一种方案什么都不装。对于j 0dp[j] 0因为没有任何物品时无法恰好装满任何正数容量的背包。最终答案dp[target]。dp[j]容量不超过j的方案数或最大价值问题中的常见定义。初始化dp[0...target] 0或根据价值初始化对于最大价值问题通常dp[0...target] 0。最终答案dp[target]可能包含了所有不超过target的方案而不是恰好等于。在计数问题中这通常不是我们想要的。对于“数字组合”问题我们必须使用“恰好装满”的定义。初始化dp[0]1是正确计数的基石。你可以这样理解当我们考虑第一个数字num时如果要凑出j num那么方案数应该是dp[num] dp[num] dp[0]。如果dp[0]不是1那么这个组合就无法被正确计数。3.2 一维DP的逆序遍历原理这是第二个关键细节也是01背包空间优化的精髓。为什么必须逆序从target遍历到num假设我们正序遍历j从num到target。考虑num 2。计算dp[2]dp[2] dp[2] dp[0]。假设初始dp[0]1,dp[2]0则更新后dp[2]1。这表示用数字2凑出容量2有一种方案。计算dp[4]dp[4] dp[4] dp[2]。注意此时的dp[2]已经是本轮更新后的值1。这意味着在计算dp[4]时我们使用的dp[2]是已经包含了当前数字2的方案数。那么dp[4] 0 1 1这个结果实际对应的方案是[2, 2]即数字2被使用了两次。这违背了01背包“每个物品最多用一次”的规则。逆序遍历可以避免这个问题计算dp[4]dp[4] dp[4] dp[2]。此时dp[2]还是上一轮未考虑当前数字2的值是0。所以dp[4] 0。计算dp[2]dp[2] dp[2] dp[0]。dp[0]1所以dp[2]1。 逆序保证了在计算dp[j]时dp[j - num]存储的是“未考虑当前物品”时的状态从而每个物品只会被计入一次。3.3 处理重复数字与组合去重题目中数组nums可能包含重复的数字例如[1, 2, 2, 5]。我们的动态规划方法会自动处理这种情况吗答案是取决于我们如何定义“不同方案”。在标准的“数字组合”问题中“不同方案”指的是选取的数字构成的集合不同与顺序无关。例如用[1, 2, 2, 5]凑target3。方案有[1,2]取第一个2和[1,2]取第二个2。这两个方案选取的数字集合都是{1, 2}在集合视角下是同一个方案。我们的动态规划方法无论是二维还是一维其本质是遍历物品数组元素。对于两个值相同的数字2它们被当作两个不同的物品来处理。因此上述算法会认为[1, nums[1]]和[1, nums[2]]是两种不同的方案从而输出2。但这通常不符合题目的要求题目一般要求计算不同的组合数而非排列数也不是考虑物品ID的选取数。那么如何得到题目通常要求的“组合数”呢关键在于遍历顺序。我们刚才的“物品遍历”是放在外层的。实际上为了得到“组合数”与物品顺序无关我们应该把**“背包容量”的循环放在外层物品的循环放在内层吗不恰恰相反。在经典的01背包计数问题中为了确保结果是“组合数”而非“排列数”我们必须把遍历物品数字的循环放在最外层**遍历背包容量的循环放在内层并且是逆序。这样做的原因是外层循环遍历物品相当于我们按顺序考虑每个物品是否加入。当我们固定了物品的考虑顺序对于同一个总和[物品A, 物品B]和[物品B, 物品A]这两种放入背包的顺序由于物品A总是在物品B之前被考虑所以只有“先考虑A再考虑B”这一种决策路径会被计算。这就保证了我们计算的是组合数而不是排列数。即使有两个相同的数字因为它们被视为不同的物品且被按顺序考虑所以由它们形成的、实质相同的集合仍然会被重复计算。要解决这个由重复元素导致的重复计数需要在遍历前对nums数组进行排序去重或者使用更复杂的状态定义记录使用某个数值的次数但这通常超出了基础01背包计数的范畴属于“有重复物品的背包”问题。在面试或笔试中如果出现重复数字务必与面试官澄清“不同方案”的定义。4. 完整代码实现与逐行分析下面我将给出基于一维DP的两种经典实现方式并附上详细的注释。我们假设问题定义是标准的计算恰好和为target的不同组合数将值相同的数字视为相同的元素即题目输入可能包含重复值但组合时认为数字值相同则不可区分这通常需要先对数组进行处理或题目保证无重复。4.1 实现一基础一维DP解法这种解法假设nums中的数字都是唯一的或者题目明确说明结果按数字组合计不考虑数字来源只考虑数值此时重复数字会导致重复组合需要预处理去重。def combinationSum4_01(nums, target): 使用一维DP数组解决01背包数字组合问题。 假设nums中数字唯一或已去重。 # 初始化dp数组dp[j]表示恰好凑成总和j的方案数 dp [0] * (target 1) # 基础情况凑成总和0的方案有一种即什么都不选 dp[0] 1 # 外层循环遍历每个数字物品 for num in nums: # 内层循环逆序遍历背包容量 # 从target遍历到num确保每个数字只被使用一次 for j in range(target, num - 1, -1): # 状态转移方程dp[j] dp[j] dp[j - num] # dp[j] (旧)不选当前数字num凑成j的方案数 # dp[j - num]选了当前数字num则剩余容量为j-num需要凑成j-num的方案数 dp[j] dp[j] dp[j - num] # 如果担心整数溢出可以在这里取模例如dp[j] (dp[j] dp[j - num]) % MOD # 最终答案就是恰好凑成target的方案数 return dp[target] # 示例 nums [1, 2, 3] target 4 print(combinationSum4_01(nums, target)) # 输出1 (只有[1,3])逐行解析dp [0] * (target 1)创建长度为target1的一维数组下标j代表要凑的总和。初始化为0。dp[0] 1这是动态规划的“种子”。凑出总和0的方案有且只有一种一个数都不选。这个初始化是“恰好装满”类问题的关键。for num in nums:外层循环遍历每一个数字。每个数字就是一个物品这个循环顺序保证了我们计算的是“组合数”。for j in range(target, num - 1, -1):内层循环逆序从target遍历到num。逆序是01背包一维优化的核心它确保了在计算dp[j]时dp[j - num]是上一轮未考虑当前数字num的状态从而每个数字只用一次。条件j num是显然的因为如果当前背包容量j连数字num都放不下那就不可能选择这个数字。dp[j] dp[j] dp[j - num]经典的状态转移。dp[j]在原值不选num的方案数基础上加上选了num的方案数dp[j - num]。return dp[target]循环结束后dp[target]存储的就是用所有数字恰好凑出target的总方案数。4.2 实现二处理可能存在的重复数字预处理去重如果题目要求将数值相同的数字视为相同的即[1,2,2]中两个2没有区别那么直接使用上面的代码对于nums [1,2,2],target3会得到错误答案2因为它区分了第一个2和第二个2。正确的答案应该是1只有[1,2]。为了得到符合通常理解的组合数我们需要在DP前对数组进行去重。但注意去重后每个数字的“数量”变成了1。然而原题可能允许重复数字但组合时认为数字相同则不可区分这本质上意味着输入数组中的重复数字是冗余信息。更严谨的做法是如果数字可重复且数量有限应使用“多重背包”的计数方法。这里我们假设题目本意是集合Set操作或者我们通过预处理来符合常见题意。def combinationSum4_01_unique(nums, target): 处理nums中可能包含重复数字的情况。 通过排序和跳过重复数字确保每个数值只被考虑一次。 这适用于“数字组合”问题中将相同数值视为同一元素的情况。 # 排序以便于跳过重复元素虽然不是必须但好习惯 nums.sort() dp [0] * (target 1) dp[0] 1 # 遍历去重后的数字 i 0 n len(nums) while i n: num nums[i] # 逆序更新DP for j in range(target, num - 1, -1): dp[j] dp[j] dp[j - num] # 跳过所有相同的数字避免重复计数 while i 1 n and nums[i 1] num: i 1 i 1 return dp[target] # 示例 nums [1, 2, 2, 3] target 4 # 组合应为[1,3] 和 [2,2]? 注意去重后nums有效为[1,2,3]所以[2,2]无法构成。 print(combinationSum4_01_unique(nums, target)) # 输出1 (只有[1,3]) # 如果希望计算[2,2]则需要用“多重背包”或“完全背包”如果2可用无限次。这个版本在遍历时跳过了连续相同的数字确保每个不同的数值只作为一件“物品”被处理一次。这符合“从一堆数字中选若干个数求和”的常见组合解释。但务必注意这与原始题目《数字组合》的输入定义可能略有差异实际做题时应以题目描述为准。5. 常见问题、调试技巧与扩展思考5.1 典型错误与排查清单在实现和调试01背包计数问题时以下几个错误非常常见初始化错误忘记将dp[0]初始化为1导致所有结果都为0。这是最常犯的错误之一。务必理解dp[0]1是组合计数问题的“空集”基础。遍历顺序错误内层循环顺序错误使用了正序for j in range(num, target1)导致每个数字被重复使用多次变成了完全背包。一定要逆序内外层循环颠倒如果错误地将容量遍历放在外层数字遍历放在内层在某些情况下计算的是“排列数”而不是“组合数”。对于标准的01背包计数数字物品遍历必须在外层。数组越界在内层循环中没有正确处理j - num的下标当j num时不应进入更新逻辑。我们的循环条件for j in range(target, num-1, -1)很好地避免了这个问题。整数溢出方案数可能非常大超过普通整型范围。如果题目要求取模一定要在每次加法操作后取模而不是最后才取模。例如dp[j] (dp[j] dp[j - num]) % MOD。对“恰好”与“不超过”理解偏差错误地将dp数组全部初始化为1或者将dp[0]之外的其他位置也初始化为1这通常对应的是“不超过容量j”的方案数初始化方式但即便如此dp[0]也应为1。仔细审题确认是“恰好等于”还是“不超过”。调试小技巧打印DP表对于小规模数据在每次外层循环处理一个数字后打印出整个dp数组。观察其变化是否符合预期。这是理解DP过程最直观的方法。手动模拟用纸笔跟踪一个简单例子如nums[1,2], target3的整个DP过程验证你的代码每一步的状态更新。边界测试target0应该返回1空集。nums为空数组除了target0返回1其他target0都应返回0。nums中所有数字都大于target结果应为0。5.2 从“方案数”到“具体方案”上述DP只给出了方案的数量。如果题目要求输出所有具体的组合方案而不仅仅是计数那么动态规划就不再是最优选择了因为DP擅长计数但存储所有具体方案的空间开销可能巨大是指数级的。这时回溯法DFS是更合适的选择。回溯可以构造出所有可能的组合并通过剪枝例如当前和超过target则返回来提高效率。虽然最坏时间复杂度仍是O(2^N)但对于需要枚举所有解的问题这是不可避免的。def combinationSum4_dfs(nums, target): 使用回溯法找出所有组合方案数字可重复使用这里假设不可重复使用。 注意此方法用于枚举所有解对于计数问题效率低于DP。 def backtrack(start, path, current_sum): if current_sum target: result.append(path[:]) # 找到一组解 return if current_sum target or start len(nums): return # 选择当前数字 path.append(nums[start]) backtrack(start 1, path, current_sum nums[start]) path.pop() # 不选择当前数字 backtrack(start 1, path, current_sum) nums.sort() # 排序有助于某些剪枝但不是必须 result [] backtrack(0, [], 0) return result nums [1, 2, 3] target 4 print(combinationSum4_dfs(nums, target)) # 输出[[1, 3]]5.3 相关变种问题与扩展理解了01背包求方案数的核心后你可以尝试解决一系列变种问题它们都是在此模型上的扩展494. 目标和给定一个整数数组nums和一个整数target向数组中的每个整数前添加或-然后串联成表达式求运算结果等于target的不同表达式数目。这可以转化为一个子集和问题背包问题。设所有添加的数字和为P添加-的数字和为N则有P - N target且P N sum(nums)。解方程得P (target sum(nums)) / 2。问题转化为在nums中找出若干个数使其和恰好等于P的方案数。这就是一个标准的01背包计数问题注意P必须为非负整数。518. 零钱兑换 II给定不同面额的硬币和一个总金额计算可以凑成总金额的硬币组合数。假设每种硬币数量无限。这不再是01背包而是完全背包的计数问题。核心区别在于内层循环的遍历顺序需要正序遍历jfromcointoamount因为同一硬币可以重复使用。涉及顺序的排列数如果题目问的是排列数即[1,2]和[2,1]算两种例如“377. 组合总和 Ⅳ”题目名是组合但实际求排列。那么就需要将背包容量的遍历放在外层物品的遍历放在内层并且内层循环为正序如果物品可无限次使用或另做处理。这颠倒了01背包求组合数的循环顺序。最后一点个人心得动态规划尤其是背包问题是算法学习的重难点。理解的关键不在于背模板而在于想清楚状态的定义以及状态之间是如何转移的。“数字组合”这个问题提供了一个绝佳的练习场让你深入理解“计数”型DP与“最值”型DP在状态转移上的微妙差异。多动手画DP表多思考为什么初始化是那样为什么遍历顺序要这样比刷十道题都管用。当你再遇到“恰好装满”、“方案总数”这些关键词时你会立刻意识到哦这又是那个熟悉的背包计数问题只是换了一件外衣而已。 
