本文总结了完全背包问题的几种常见变体及其动态规划解法:
- **求组合数**(如零钱兑换II):外层循环遍历物品,内层循环遍历背包容量。
- **求排列数**(如组合总和Ⅳ、爬楼梯进阶版):外层循环遍历背包容量,内层循环遍历物品。
- **求最小物品数**(如零钱兑换、完全平方数):使用 `dp[j] = min(dp[j - coins[i]] + 1, dp[j])` 递推。
关键代码中,组合/排列数通过 `dp[i] += dp[i - nums[j]]` 累计方案数,最小数问题则取最小值更新。