动态规划
解题思路
确定 dp 数组以及下标的含义：dp[j]：凑成总金额 j 的最少个数为 dp[j]
确定递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j])
- 凑足总额为 j - coins[i] 的最少个数为 dp[j - coins[i]]，那么只需要加上一个钱币 coins[i] 即 dp[j - coins[i]] + 1 就是 dp[j]；
- 所以 dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的；
如何初始化 dp 数组：首先凑足总金额为 0 所需钱币的个数一定是 0，那么 dp[0] = 0
确定遍历顺序：
- 0-1 背包 参考 上一行 的值，使用一维数组压缩空间的时候，倒序 填表；
- 完全背包 参考 当前行 的值，使用一维数组压缩空间的时候，正序 填表；
举例推导 dp 数组：以 coins = [1, 2, 5]，amount = 5 为例：
金额总和 j = 0 金额总和 j = 1 金额总和 j = 2 金额总和 j = 3 金额总和 j = 4 金额总和 j = 5 硬币面值为 0 0 Infinity Infinity Infinity Infinity Infinity 硬币面值为 1 0 1 2 3 4 5 硬币面值为 2 0 1 1 2 2 3 硬币面值为 3 0 1 1 2 2 1
实现代码
const coinChange = (coins, amount) => {
if (amount === 0) return 0;
// 1. 声明 dp
let dp = Array(amount + 1).fill(Infinity);
// 2. 初始化 dp
dp[0] = 0;
for (let i = 0; i < coins.length; i++) { // 物品
for (let j = coins[i]; j <= amount; j++) { // 背包
dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 377. 组合总和 Ⅳ
上一篇
评论
