Posted on 2023-09-09 17:12
Uriel 閱讀(57)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
求問用數組nums里面的數字湊成相加之和為target的方式有多少種（不同順序算不同方法，每個數字可以無限次數用），DP
1 #377
2 #Runtime: 22 ms (Beats 67.7%)
3 #Memory: 13.4 MB (Beats 38.41%)
4
5 class Solution(object):
6 def combinationSum4(self, nums, target):
7 """
8 :type nums: List[int]
9 :type target: int
10 :rtype: int
11 """
12 dp = [0] * (target + 1)
13 dp[0] = 1
14 for i in range(1, target + 1):
15 for x in nums:
16 if i - x >= 0:
17 dp[i] += dp[i - x]
18 return dp[target]