【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();      }  };