Posted on 2023-09-09 17:12
Uriel 閱讀(41)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
DP 、
閑來(lái)無(wú)事重切Leet Code
求問(wèn)用數(shù)組nums里面的數(shù)字湊成相加之和為target的方式有多少種（不同順序算不同方法，每個(gè)數(shù)字可以無(wú)限次數(shù)用），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]