Cocolib组合总和 Ⅳ
TIP
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
思路
动规五部曲
- 确定dp数组以及下标的含义：
dp[i]：总和 = i时的组合数。 - 确定递推公式：
dp[j]=dp[j-nums[i]]+dp[i] - dp数组如何初始化：
dp[0] = 1、dp[非0] = 0 - 确定遍历顺序
- 举例推导dp数组
js
var combinationSum4 = function(nums, target) {
if(nums.length===1) return 0
let dp = Array(target + 1).fill(0)
dp[0] = 1
for(let j=0;j<=target;j++){
for(let i=0;i<nums.length;i++){
if(j-nums[i]>=0)
dp[j] += dp[j-nums[i]]
}
}
console.log(dp)
return dp[target]
};