562. 背包问题 IV

562. 背包问题 IV

中文English

给出 n 个物品, 以及一个数组, nums[i]代表第i个物品的大小, 保证大小均为正数并且没有重复, 正整数 target 表示背包的大小, 找到能填满背包的方案数。
每一个物品可以使用无数次

样例

样例1

输入: nums = [2,3,6,7] 和 target = 7
输出: 2
解释:
方案有: 
[7]
[2, 2, 3]

样例2

输入: nums = [2,3,4,5] 和 target = 7
输出: 3
解释:
方案有: 
[2, 5]
[3, 4]
[2, 2, 3]

 

 

输入测试数据 (每行一个参数)如何理解测试数据？

 版本：动态规划  背包类型DP 

class Solution:
    """
    @param nums: an integer array and all positive numbers, no duplicates
    @param target: An integer
    @return: An integer
    """
    def backPackIV(self, nums, target):
        # write your code here
        #计算个数
        
        length = len(nums)
        dp = [[0 for _ in range(target + 1)] for _ in range(length + 1)]
        
        #如果target为0的话，则个数为1
        for i in range(length + 1):
            dp[i][0] = 1
        
        #计算顺序
        for i in range(1, length + 1):
            for j in range(1, target + 1):
                #不确定有多少次
                count = 0 
                while count*nums[i - 1] <= j:
                    #如果是j - nums[i - 1]*count 没有找到的话，说明是不存在的，则加的是0，否则加的是当前
                    #组成该数的个数是多少,比如4，存在2,4两个物品，则有两种可能
                    dp[i][j] += dp[i - 1][j - nums[i - 1]*count]
                    count += 1 
        
        return dp[length][target]