【leetcode刷题】T170-组合总和 Ⅳ

• 2019 年 10 月 7 日
• 筆記

木又连续日更第7天（7/100）

动态规划类型第15篇解题报告

leetcode第377题：组合总和 Ⅳ

https://leetcode-cn.com/problems/combination-sum-iv/

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:  nums = [1, 2, 3]  target = 4  所有可能的组合为：  (1, 1, 1, 1)  (1, 1, 2)  (1, 2, 1)  (1, 3)  (2, 1, 1)  (2, 2)  (3, 1)  请注意，顺序不同的序列被视作不同的组合。  因此输出为 7。  

【思路】

使用数组dp[i]来存储满足条件的组合个数，对于nums数组中的元素n，当i > n时，dp[i] = sum(dp[i-n])。

【代码】

python版本

class Solution(object):      def combinationSum4(self, nums, target):          """          :type nums: List[int]          :type target: int          :rtype: int          """          dp = [0] * (target + 1)          dp[0] = 1          for i in range(1, target + 1):              for n in nums:                  if i >= n:                      dp[i] += dp[i - n]          return dp[-1]  

C++版本

class Solution {  public:      int combinationSum4(vector<int>& nums, int target) {          vector<double> dp(target+1, 0);          dp[0] = 1;          for(int i=1; i <= target; i++){              for(auto n: nums){                  if(i >= n)                      dp[i] += dp[i - n];              }          }          return dp.back();      }  };