494目标和

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 经典 0-1 背包问题。
        # 拆解题意，就是 把nums分成两部分，一个 正包，一个 负包，
        # 正包和 + 负包和 = sum(nums)； 正包和 - 负包和 = target；
        # 由上面两个式子可知，正包和 = (sum + target)/2  ----> 如果是整数说明可以成功，如果好似小数，则说明无法凑出这样的正包和，此时运算结果不管怎么折腾都到达不了 target 。
        # 由于 sum 和 target 都是确定的数，"正包和 也就是一个定数，
        # 问题转化为：求nums中有多少种方法凑出一个这样的正包和，正包和就可视为容量（经典 0-1 背包问题，只拿1次是0-1，不限次数是完全）
        # 固定容量 ，求凑的方法数量。

        # 设定 d[j] 为 j容量的背包，有d[j]种组合方法;
        # 从实际例子分析： 容量j=5时，可以分成5种情况，
        # 情况一：（1个数被固定，有d[j-1]种方法 配合这1个固定的数凑“正包和”）    可以回头看定义，d[j] 
        # 情况二：（2个数被固定，有d[j-2]种方法 配合这2个固定的数凑“正包和”）# 情况三：（3个数被固定，有d[j-3]种方法 配合这3个固定的数凑“正包和”）# ... （j个数被固定，有d[j-j=0]种方法 配合这j个固定的数凑“正包和”）
        # 以上所有情况求和 就是 d[j]的组合方法数。
        # d[j] += d[j-weight[i]]     i 的 value 和 weight 还是公用一套 nums。
        # 初始化 d[统一] = 0 不影响递推 ； d[0] = 1 , 若设第一个位置定为0 递推导致全部为0。 合理的逻辑解释应该是容量为0，有一个不放的组合方式，哈哈，虽然解释有点牵强。
        v = (sum(nums)+target)/2
        if v - int(v) != 0 or v<0: return 0         # 小数说明无法凑出这样的正包和，怎么折腾都到达不了 target。
        d = [ 0 for _ in range(int(v)+1) ]
        d[0] = 1
        for i in range(len(nums)):                   # 0-1完全背包 还是先物品，再倒序遍历背包；
            for j in range(int(v),nums[i]-1,-1):
                d[j] += d[j-nums[i]]
        print(d)
        return d[int(v)]