377组合总和Ⅳ

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # 又是固定 背包容量 target，求 有多少种方法凑。
        # 非常类似于 《518零钱兑换二》，也是一个这样的完全背包问题，但是这里凑法和顺序有关，属于排列而不是组合，因此遍历顺序不会先固定物品，因此先遍历背包再遍历物品，由于是完全背包拿的次数不限，背包是正序遍历。
        d = [0 for _ in range(target+1)]
        d[0] = 1
        for j in range(1,target+1):
            for i in range(len(nums)):
                if j>=nums[i]:         # 还是要保证 j-weight[i]>=0 这是递推公式先决条件
                    d[j] += d[j-nums[i]]
                # print(d)         
        return d[target]