组合总和 Ⅳ
lkj 4/22/2022 动态规划背包
# 题目 LeetCode (opens new window)
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3
输出：0
# 代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var combinationSum4 = function (nums, target) {
// 1. 确定 dp 数组以及下标的含义
// dp[j] 表示在nums数组中选择若干个元素，使得这些元素之和为 j 的元素组合个数
// 2. 确定状态转移方程，对于nums数组中的每个元素nums[i]（小于j）都可以选择
// 那么就有 dp[j-nums[i]]，将所有 dp[j-nums[i]] 相加即为 dp[j]
// dp[j] += dp[j-nums[i]] 的累加
// 3. 确定 dp 数组的初始化
// dp[0] = 1
// 4. 确定 dp 数组的遍历顺序，由于每个元素可以选择多次，所以可以确定是完全背包问题
// 纯粹的完全背包问题既可以先遍历物品再遍历背包容量，也可以先遍历背包容量再遍历物品
// 但是这题很特殊，强调元素顺序，求的是排列数，只能是先遍历背包容量再遍历物品
// 4. 返回最终的解
// dp[target]
let len = nums.length;
const dp = new Array(target + 1).fill(0);
dp[0] = 1;
for (let j = 1; j <= target; j++) { // 先遍历背包容量(目标和 j)
for (let i = 0; i < len; i++) { // 再遍历物品（数组元素）
if (j >= nums[i]) {
dp[j] += dp[j - nums[i]]
}
}
}
return dp[target]
};
# 总结
通过 零钱兑换 II 和 组合总和 IV 这两道题我们可以总结出完全背包问题的两个注意事项
- 若是求组合数，需要先遍历物品再遍历背包容量
- 若是求排列数，需要先遍历背包容量再遍历物品
关于为什么先遍历物品再遍历背包容量、先遍历背包容量再遍历物品所造成最终结果的不同可以通过画图举例来验证一下，印象可能会更加深刻些
所谓的组合，并不强调元素的先后顺序，比如
所谓的排列，会强调元素的先后顺序，比如
并且它们的递推公式都是
此时，你再重新做下 爬楼梯 这题（可能需要你对原题进行改动），要求采用完全背包的动态规划解法进行解答，相信我，你会有不一样的收获的