Posted on 2023-09-09 17:12
Uriel 阅读(13)
评论(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]