记忆化搜索
解题思路
定义 dfs(i, c) 表示用前 i 种硬币组成金额 c 的方案数，考虑 选或不选 有：dfs(i, c) = dfs(i − 1, c) + dfs(i, c − coins[i])
- 不再继续选第 i 种硬币：dfs(i − 1, c)；
- 继续选一枚第 i 种硬币：dfs(i, c − coins[i])；
递归边界：dfs(−1, 0) = 1, dfs(−1, >0) = 0
实现代码
var change = function (amount, coins) {
const dfs = (i, c) => {
// 终止条件
if (i < 0) return c == 0 ? 1 : 0;
// 从备忘录中取出存储的结果
if (memo[i][c] != -1) return memo[i][c];
// 当前硬币大于总和，则 不放入硬币
if (c < coins[i]) return memo[i][c] = dfs(i - 1, c);
// 当前硬币小于总和，则返回「上一次不选当前硬币」+「当前选择硬币」
return memo[i][c] = dfs(i - 1, c) + dfs(i, c - coins[i]);
}
// 1. 初始化二维数组备忘录，存储搜索结果
const memo = new Array(coins.length).fill(0).map(it => new Array(amount + 1).fill(-1));
return dfs(coins.length - 1, amount);
};
动态规划
解题思路
确定 dp 数组以及下标的含义：dp[j]：凑成总金额 j 的货币组合数为 dp[j]
确定递推公式：dp[j] 就是所有的 dp[j - coins[i]] 相加
如何初始化 dp 数组：初始化 dp[0]=1，只有当不选取任何硬币时，金额之和才为 0，因此只有 1 种硬币组合
确定遍历顺序：
- 0-1 背包 参考 上一行 的值，使用一维数组压缩空间的时候，倒序 填表；
- 完全背包 参考 当前行 的值，使用一维数组压缩空间的时候，正序 填表；
举例推导 dp 数组：以 coins = [1, 2, 5]，amount = 5 为例：
金额总和 j = 0 金额总和 j = 1 金额总和 j = 2 金额总和 j = 3 金额总和 j = 4 金额总和 j = 5 硬币面值为 0 1 0 0 0 0 0 硬币面值为 1 1 1 1 1 1 1 硬币面值为 2 1 1 2 2 3 3 硬币面值为 3 1 1 2 2 3 4
复杂度
-
时间复杂度：
O(amount * n)，其中 amount 是总金额，n 是数组 coins 的长度； -
空间复杂度：
O(amount)，其中 amount 是总金额，需要创建长度为 amount + 1 的数组 dp；
代码实现
JavaScript
JavaScript
var change = function (amount, coins) {
// 1. 声明 dp
const dp = new Array(coins.length + 1).fill(0).map(it => new Array(amount + 1).fill(0));
// 2. 初始化 dp
dp[0][0] = 1;
for (let i = 0; i < coins.length; i++) { // 物品
for (let c = 0; c <= amount; c++) { // 背包
if (c < coins[i]) {
dp[i + 1][c] = dp[i][c];
} else {
dp[i + 1][c] = dp[i][c] + dp[i + 1][c - coins[i]];
}
}
}
return dp[coins.length][amount];
};
// 空间压缩
var change = function (amount, coins) {
// 1. 声明 dp 数组
const dp = new Array(amount + 1).fill(0);
// 2. 初始化 dp[0]=1，只有当不选取任何硬币时，金额之和才为 0，因此只有 1 种硬币组合
dp[0] = 1;
for (let i = 0; i < coins.length; i++) {
for (let j = coins[i]; j <= amount; j++) {
// dp[j] 表示金额之和等于 x 的硬币组合数
dp[j] = dp[j] + dp[j - coins[i]];
}
}
return dp[amount];
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 474. 一和零
上一篇
评论
