完全背包问题 518：LeetCode 零钱兑换 II 与 OJ 1273 方案数求解的 3 点核心差异

完全背包问题深度解析LeetCode 518与OJ 1273的三大核心差异在算法竞赛和面试中完全背包问题是一个经典且高频的动态规划问题。本文将聚焦于LeetCode 518题零钱兑换II与信息学奥赛OJ 1273题货币系统的深度对比分析揭示它们在题目表述、边界条件和状态定义上的关键差异。1. 问题定义与状态转移的对比完全背包问题的核心在于每种物品可以无限次使用。LeetCode 518和OJ 1273虽然都基于这一模型但在具体实现上存在显著差异。1.1 状态定义差异两题的状态定义表面相似实则暗藏玄机OJ 1273dp[i][j]表示前i种货币凑j元的方案数LeetCode 518dp[i][j]表示前i种硬币凑j金额的组合数看似相同但关键在于问题约束的不同# OJ 1273的状态转移方程 dp[i][j] dp[i-1][j] dp[i][j-a[i]] # 需要判断j a[i] # LeetCode 518的状态转移方程 dp[i][j] dp[i-1][j] dp[i][j-coins[i-1]] # 注意coins的索引差异1.2 初始化条件对比初始化是动态规划的关键步骤两题在此有明显区别初始化要素OJ 1273LeetCode 518金额为0时的方案数dp[i][0] 1所有idp[0][0] 1无硬币时的方案数题目保证n≥1dp[0][j] 0j0注意OJ 1273明确说明结果需要用long long表示而LeetCode 518保证结果在32位有符号整数范围内。2. 数据类型与数值范围的工程考量在实际编码中数据类型的选择直接影响程序的正确性。2.1 数据范围对比题目货币/硬币数量目标金额范围结果范围OJ 1273n≤15m≤4000可能超过2^31LeetCode 5181≤n≤3001≤amount≤5000保证在32位整数内2.2 代码实现差异由于数据范围的差异两题的实现方式也不同// OJ 1273必须使用long long long long dp[N][M]; // N25, M4005 // LeetCode 518可以使用int int dp[amount1]; // amount≤5000关键点OJ题目通常不限制数据范围需要选手自行判断而LeetCode会明确给出约束条件。3. 滚动数组优化的不同实现空间优化是动态规划的常见技巧但两题在优化时需要注意不同细节。3.1 二维转一维的实现# OJ 1273的优化版本 dp [0]*(m1) dp[0] 1 for i in range(1, n1): for j in range(a[i], m1): # 正序遍历 dp[j] dp[j-a[i]] # LeetCode 518的优化版本 dp [0]*(amount1) dp[0] 1 for coin in coins: for j in range(coin, amount1): # 正序遍历 dp[j] dp[j-coin]虽然代码结构相似但有以下细微差别OJ 1273的货币数组索引从1开始LeetCode 518直接遍历coins数组3.2 遍历顺序的陷阱在完全背包问题中遍历顺序至关重要错误的倒序遍历会变成01背包问题每种物品只能选一次正确的正序遍历保证每种物品可以重复选择# 错误示例倒序遍历会得到错误结果 for coin in coins: for j in range(amount, coin-1, -1): # 这是01背包的写法 dp[j] dp[j-coin]4. 实战代码对比分析让我们看两题的完整AC代码体会它们的异同。4.1 OJ 1273题解#includebits/stdc.h using namespace std; #define N 25 #define M 4005 long long m, n, dp[M], a[N]; // 必须用long long int main() { cin n m; for(int i 1; i n; i) cin a[i]; dp[0] 1; // 初始化 for(int i 1; i n; i) for(int j a[i]; j m; j) dp[j] dp[j-a[i]]; cout dp[m]; return 0; }4.2 LeetCode 518题解class Solution { public int change(int amount, int[] coins) { int[] dp new int[amount1]; dp[0] 1; for (int coin : coins) { for (int j coin; j amount; j) { dp[j] dp[j-coin]; } } return dp[amount]; } }4.3 关键差异总结特性OJ 1273LeetCode 518输入处理货币数量n和金额m分开读取直接给coins数组和amount数组索引通常从1开始从0开始数据类型必须使用long longint足够初始化方式显式初始化dp[0]1同左结果返回直接输出dp[m]返回dp[amount]5. 常见错误与调试技巧在解决这两类问题时容易陷入以下陷阱混淆完全背包与01背包忘记正序遍历背包容量完全背包for(jcoin; jamount; j)01背包for(jamount; jcoin; j--)初始化错误忘记初始化dp[0]1错误地将所有dp[i][0]初始化为1仅一维数组需要整数溢出在OJ题目中未使用long long导致WALeetCode中虽然保证不溢出但在其他平台可能需要注意索引偏移OJ题目常用1-based索引LeetCode常用0-based索引调试建议当结果不正确时先打印出小规模测试用例的整个dp表检查状态转移是否符合预期。6. 算法扩展与变种完全背包问题有许多变种理解这两题的差异有助于解决其他相关问题最少硬币问题LeetCode 322求凑成金额的最少硬币数状态转移方程dp[j] min(dp[j], dp[j-coin]1)组合总和IVLeetCode 377考虑顺序不同的方案为不同组合需要先遍历背包容量再遍历物品二维费用背包每个物品有两个维度的费用限制需要三维dp数组或优化后的二维数组# 组合总和IV的解法注意遍历顺序 dp [0]*(target1) dp[0] 1 for j in range(1, target1): # 先遍历背包 for num in nums: # 再遍历物品 if j num: dp[j] dp[j-num]7. 性能分析与优化虽然两题的时间复杂度都是O(n*amount)但在实际实现中仍有优化空间提前排序对coins数组排序可以提前终止内层循环Arrays.sort(coins); for (int coin : coins) { if (coin amount) break; for (int j coin; j amount; j) { dp[j] dp[j-coin]; } }空间优化一维数组比二维数组更节省空间但要注意遍历顺序输入优化在OJ中使用更快的输入方式如scanf代替cin在LeetCode中这通常不重要8. 数学视角下的完全背包从生成函数的角度看完全背包问题等价于求特定形式的幂级数展开对于OJ 1273方案数实际上是求 $$ G(x) \prod_{i1}^n \left(1 x^{a_i} x^{2a_i} \cdots\right) \prod_{i1}^n \frac{1}{1-x^{a_i}} $$ 中$x^m$项的系数。而动态规划的方法实际上是按递推方式计算这个系数避免了直接进行复杂的数学运算。9. 多语言实现对比不同语言在实现这两题时也有各自的特点9.1 Python实现# LeetCode 518 def change(amount, coins): dp [0] * (amount 1) dp[0] 1 for coin in coins: for j in range(coin, amount 1): dp[j] dp[j - coin] return dp[amount]9.2 Go实现// OJ 1273风格 func moneySystem(n, m int, a []int) int64 { dp : make([]int64, m1) dp[0] 1 for i : 0; i n; i { for j : a[i]; j m; j { dp[j] dp[j-a[i]] } } return dp[m] }9.3 JavaScript实现// LeetCode 518 var change function(amount, coins) { const dp new Array(amount1).fill(0); dp[0] 1; for (const coin of coins) { for (let j coin; j amount; j) { dp[j] dp[j-coin]; } } return dp[amount]; };10. 实际应用场景完全背包问题在现实中有广泛的应用货币兑换银行系统中的零钱兑换方案计算资源分配云计算中的资源分配问题库存管理商品组合优化密码学某些加密算法的密钥组合问题理解这类问题的核心差异有助于我们在实际工程中选择合适的算法和数据结构。