从‘包子凑数’到‘硬币问题’动态规划入门用Java彻底搞懂无限背包第一次接触动态规划时很多人会被各种背包问题绕得晕头转向。特别是当题目从每个物品只能选一次的0-1背包变成物品可以无限取用的完全背包时状态转移方程似乎突然变得难以捉摸。我在准备算法竞赛时就深有体会——那些讲解0-1背包的教程铺天盖地但一旦遇到像包子凑数、零钱兑换这类无限取用的问题参考资料就少得可怜。1. 问题本质当动态规划遇见数论让我们从一个看似简单的蓝桥杯经典题开始给定几种不同规格的蒸笼每个蒸笼可以放任意数量的包子视为无限供应。问不能凑出的包子数量中最小的那个是多少如果所有数量都能凑出输出INF。这个问题表面上是生活化的包子凑数实则暗藏两个关键技术点完全背包模型每种蒸笼规格相当于物品体积包子数量相当于背包容量且每种物品无限供应数论基础需要先判断是否有解这涉及到裴蜀定理Bézouts identity1.1 裴蜀定理判断是否有解的关键在写任何DP代码之前我们必须先回答给定的包子规格能否凑出任意正整数这直接决定了我们是否需要输出INF。裴蜀定理告诉我们对于不全为零的整数a₁, a₂,...,aₙ存在整数x₁, x₂,...,xₙ使得a₁x₁ a₂x₂ ... aₙxₙ gcd(a₁, a₂,...,aₙ)应用到包子问题中如果所有包子规格的最大公约数gcd 1那么只能凑出gcd的倍数如果gcd 1则存在足够大的N使得所有n ≥ N都能被凑出Java实现gcd计算public int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } // 计算多个数的gcd public int multiGcd(int[] nums) { int res nums[0]; for (int num : nums) { res gcd(res, num); if (res 1) break; // 提前终止 } return res; }1.2 从数论到动态规划的过渡当gcd1时我们需要找出最大的不可凑数称为硬币问题或邮票问题。数学上已知对于两个互质的数a和b最大不可凑数为ab-a-b。但对于更多数字的情况就需要动态规划出马了。2. 完全背包的DP建模与传统0-1背包不同完全背包允许无限次选取每个物品。这导致状态转移时需要考虑同一物品的多次选取。2.1 状态定义与转移方程设dp[i]表示凑出数量i所需的最少包子个数或者是否能凑出i视具体问题而定。对于包子凑数问题我们可以简化为能否凑出boolean[] dp new boolean[10000]; // 足够大的上界 dp[0] true; // 边界条件凑出0不需要任何包子 for (int num : nums) { // nums是包子规格数组 for (int i num; i dp.length; i) { dp[i] | dp[i - num]; // 状态转移 } }这个模板与0-1背包的核心区别在于内层循环的顺序0-1背包逆序遍历容量防止重复选取完全背包正序遍历容量允许重复选取2.2 空间优化与遍历顺序理解遍历顺序是掌握完全背包的关键。让我们对比两种写法0-1背包写法错误示范for (int i 0; i nums.length; i) { for (int j nums[i]; j target; j) { dp[j] dp[j - nums[i]]; } }完全背包正确写法for (int num : nums) { for (int j num; j target; j) { dp[j] dp[j - num]; } }看似只是循环顺序的微小差别实则暗藏玄机。正序遍历时dp[j-num]可能已经包含当前num的选取因此实现了重复选取。3. 实战对比LeetCode经典问题理解了基础模型后让我们看几个变种问题体会其中的异同。3.1 零钱兑换LeetCode 322题目给定不同面额的硬币和一个总金额计算可以凑成总金额的最少硬币数。public int coinChange(int[] coins, int amount) { int[] dp new int[amount 1]; Arrays.fill(dp, amount 1); // 初始化为不可能的大值 dp[0] 0; for (int coin : coins) { for (int i coin; i amount; i) { dp[i] Math.min(dp[i], dp[i - coin] 1); } } return dp[amount] amount ? -1 : dp[amount]; }与包子问题的区别求的是最少硬币数而非能否凑出需要处理无解情况返回-13.2 组合总和IVLeetCode 377题目给定一个由不同整数组成的数组找出和为target的组合的个数顺序不同视为不同组合。public int combinationSum4(int[] nums, int target) { int[] dp new int[target 1]; dp[0] 1; for (int i 1; i target; i) { for (int num : nums) { if (i num) { dp[i] dp[i - num]; } } } return dp[target]; }这个变种展示了完全背包用于计数问题内外层循环交换带来的不同含义顺序敏感4. 通用解题框架与优化技巧经过以上案例我们可以总结出解决无限凑数问题的通用步骤数论检查计算所有数字的gcd根据问题要求判断是否需要处理INF情况DP初始化设置足够大的上界数学上已知对于n个数最大不可凑数不超过max(nums)^2初始化dp数组通常dp[0] true或0状态转移正序遍历容量关键区别根据问题类型选择状态转移方程可行性问题dp[i] | dp[i-num]最优化问题dp[i] min/max(dp[i], dp[i-num]cost)计数问题dp[i] dp[i-num]结果提取扫描dp数组寻找答案处理边界情况性能优化技巧提前排序有时排序后可以提前终止循环空间优化通常只需一维数组数学剪枝利用数论知识减少计算量// 优化后的包子问题完整解法 public int minImpossibleNumber(int[] nums) { // 第一步检查gcd int g nums[0]; for (int num : nums) g gcd(g, num); if (g ! 1) return -1; // 或处理INF // 第二步DP求解 int maxNum 0; for (int num : nums) maxNum Math.max(maxNum, num); boolean[] dp new boolean[maxNum * maxNum 1]; dp[0] true; for (int num : nums) { for (int i num; i dp.length; i) { if (dp[i - num]) dp[i] true; } } // 第三步找最大不可凑数 for (int i dp.length - 1; i 0; i--) { if (!dp[i]) return i; } return -1; }在实际刷题中我发现很多同学容易陷入两个误区一上来就写DP忽略数论前置判断混淆0-1背包和完全背包的遍历顺序记住这个口诀0-1背包倒着走完全背包正着来gcd检查不能少。掌握了这个模式后这类问题就变得有迹可循了。