leetcode动态规划（十七）-组合总和IV

题目

377.组合总和IV

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• nums 中的所有元素 互不相同
• 1 <= target <= 1000

思路

从题目给的例子可以看出来每个元素可以取无数次，本题就是完全背包问题

题目中：顺序不同的序列被视作不同的组合，即说明求的是排列，序列不同算不同的组合

动规五步曲

1.确定dp的定义

dp[j]表示背包容量为target的背包装满后有dp[j]种方法

2.确定递推公式

dp[j]（考虑nums[i]）可以由 dp[j - nums[i]]（不考虑nums[i]） 推导出来。

因为只要得到nums[j]，排列个数dp[i - nums[j]]，就是dp[i]的一部分。

递推公式为dp[j] +=dp[j-nums[i]]

3.初始化

初始化dp[0] = 1，要不为0的话后面就全部都是0了，相加也没有用了，是根据力扣平台的测试用例推测出来的，dp[0]=1没有实际意义，纯粹就是为了递推公式

4.确定递推顺序

因为是求排列，所以要先遍历背包，再遍历物品

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

5.打印dp数组

代码 

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        if min(nums)>target:
            return 0
        dp = [0]*(target+1)
        dp[0] = 1
        for j in range(1,target+1):
            for i in range(len(nums)):
                if j >= nums[i]:#这里需要做判断，如果物品重量大于背包容量，就直接跳过本次累加
                    dp[j] += dp[j-nums[i]]
        return dp[-1]