416. 分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

0-1背包问题：背包容量为m，物品有大小和价值两种属性，求背包最大能装多少价值的物品？	0-1背包问题变体（分割等和子集）：背包容量为total/2, 每个物品的大小为 nums[i] 。对于前i个物品，是否有一种装法，能恰好装满背包？
dp[i][j] 表示对前i个物品，背包容量为j时，可以装的最大价值	dp[i][j] 表示对前i个物品，背包容量为j时，值为True/ False (能否装满)

dp数组行和列都分别增加1，第0列表示背包容量为0，第0行表示（虚拟）物品重量为0（这样做，方便初始化dp数组以及后续dp状态转移）
由于加了虚拟的0行和0列，物品i从 1 开始，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i-1]

class Solution(object):
    def canPartition(self, nums):
        total=sum(nums) # total为列表之和
        if total%2!=0:return False # 若无法被2整除，说明无法等和，直接返回False

        # 行和列都分别增加1，第0列表示背包容量为0，第0行表示（虚拟）物品重量为0
        # 这样做，方便初始化dp数组以及后续dp状态转移
        dp=[[False for _ in range(total/2 + 1)] for _ in range(len(nums)+1)]
        for i in range(len(nums)+1):# 和为0时，第一列为True
            dp[i][0]=True
        for i in range(1,len(nums)+1):
            for j in range(1,total/2 + 1):
                if j<nums[i-1]: # 若背包容量超过物品大小，装不下
                    dp[i][j] = dp[i - 1][j] # 继承之前的结果
                else: # 继承之前装下/装不下的结果（只要之前有True，dp[i][j]就为True）
                    dp[i][j]= dp[i-1][j] | dp[i-1][j-nums[i-1]]
        return dp[-1][-1]