leetcode_377

发表于   |   分类于

Combination Sum IV

题目戳这

题意

给定一个数组a和目标整数target，问有几种方法使得a数组中的任意多个元素之和等于target，每个元素可以用任意多次。

解法

这就是比较简单的dp题目，不过我dp一直比较渣，，所以也得记录下。我们用dp[x]来表示加到x这个数字的方法数，那么对于任意一个数组中的元素p,如果x>=p,则 dp[x] = dp[x]+dp[x-p]，搞一个二重循环即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        res = [0]*(target+1)
        res[0] = 1
        
        for i in range(len(res)):
            for y in nums:
                if i >= y:
                    res[i] += res[i-y]
                    
           
        return res[target]