背包型动态规划——背包问题6

阳光穿透心脏的1/2处 2022-10-27 12:06 178阅读 0赞

#  #

给出一个都是正整数的数组 `nums`，其中没有重复的数。从中找出所有的和为 `target` 的组合个数。

**示例：**

输入: nums = [1, 2, 4] 和 target = 4
    输出: 6
    解释:
    可能的所有组合有：
    [1, 1, 1, 1]
    [1, 1, 2]
    [1, 2, 1]
    [2, 1, 1]
    [2, 2]
    [4]

### 1、题目分析 ###

和背包问题5唯一的区别是：组合中数字可以按照不同的顺序组合

### 2、确定状态 ###

最后一步：最后一个物品重量是多少

• 如果最后一个物品重量是A0 , 则要求有多少种组合能拼成Target – A0

• 如果最后一个物品重量是A1 , 则要求有多少种组合能拼成Target – A1

• …

• 如果最后一个物品重量是AN-1, 则要求有多少种组合能拼成Target – AN-1

因此我们可以假设f\[i\]表示有多少种组合能拼出重量i

### 3、转移方程 ###

假设f\[i\]表示有多少种组合能拼出重量i  
![在这里插入图片描述][2021020322134598.png]

### 4、初始条件和边界情况 ###

f\[0\]=1：表示有1种组合能拼出重量0

如果i<Aj，则对应的f\[i-Aj\]不加入f\[i\]

### 5、计算顺序 ###

从小到大计算，结果为f\[Target\]

时间复杂度: O(N\*Target)，空间复杂度：O(Target)

### 6、代码实现 ###

class Solution:
        """ @param nums: an integer array and all positive numbers, no duplicates @param target: An integer @return: An integer """
        def backPackVI(self, nums, target):
            # write your code here
            if target==0 or len(nums)==0:
                return 0
            dp=[0]*(target+1)
            dp[0]=1
            for i in range(1,target+1):
                for j in nums:
                    if i>=j:
                        dp[i]+=dp[i-j]
            return dp[target]

#  #

[2021020322134598.png]: /images/20221024/68a000bf966e43f3b742b1485ce2ac36.png