leetcode 377. 组合总和 Ⅳ #动态规划

[webVueBlog]

377. 组合总和 Ⅳ

[webVueBlog]

377. 组合总和 Ⅳ

/*
 * @lc app=leetcode.cn id=377 lang=javascript
 *
 * [377] 组合总和 Ⅳ
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
target = 4
dp[4] 和为4的组合数
dp[4] = dp[3]+1  + dp[2]+2 + dp[1]+3 + dp[0][4]

dp[4] = dp[3]+1 + dp[2]+2 + dp[1]+3 + dp[0][4] // 4 + 2 + 1 = 7
dp[3] = dp[2]+1 + dp[1]+2 + dp[0]+3 // 2 + 1 + 1 = 4
dp[2] = dp[1]+1 + dp[0]+2 // 1 + 1 = 2
dp[1] = dp[0]+1 // 1
dp[0] = 1 [0] // 1
(56 ms)
 */
var combinationSum4 = function(nums, target) {
 let dp = new Array(target+1).fill(0);
 dp[0] = 1;
 // 1-target
 for(let i = 1; i <= target; i++) {
  for(let j = 0; j < nums.length; j++) {
   if(i - nums[j] >= 0) {
    dp[i] += dp[i-nums[j]];
   }
  }
 }
 return dp[target];
};
// @lc code=end