动态规划
解题思路
确定 dp 数组以及下标的含义：dp[i]: 凑成目标正整数为 i 的排列个数为 dp[i]
确定递推公式：dp[i] = dp[i] + dp[i - nums[j]]
如何初始化 dp 数组：初始化 dp[0]=1，只有当不选取任何物品时，总和才为 0，因此只有 1 种组合
确定遍历顺序：
- 0-1 背包 参考 上一行 的值，使用一维数组压缩空间的时候，倒序 填表；
- 完全背包 参考 当前行 的值，使用一维数组压缩空间的时候，正序 填表；
举例推导 dp 数组：以 nums = [1, 2, 3]，target = 4 为例：
背包容量为 i = 0 背包容量为 i = 1 背包容量为 i = 2 背包容量为 i = 3 背包容量为 i = 4 dp[0] 1 0 0 0 0 dp[1] 1 1 0 0 0 dp[2] 1 1 2 0 0 dp[3] 1 1 2 4 0 dp[4] 1 1 2 4 7
复杂度
-
时间复杂度：
O(target * n)，其中 target 是目标值，n 是数组 nums 的长度； -
空间复杂度：
O(target)，需要创建长度为 target + 1 的数组 dp；
实现代码
var combinationSum4 = function (nums, target) {
// 1. 声明 dp 数组
const dp = new Array(target + 1).fill(0);
// 2. 初始化 dp[0]=1，只有当不选取任何物品时，总和才为 0，因此只有 1 种组合
dp[0] = 1;
for (let i = 0; i <= target; i++) { // 先遍历背包
for (let j = 0; j < nums.length; j++) { // 遍历物品
if (i >= nums[j]) { // 物品小于等于背包剩余容量，才可以放入背包
dp[i] = dp[i] + dp[i - nums[j]];
}
}
}
return dp[target];
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 518. 零钱兑换Ⅱ
上一篇
评论
