416. 分割等和子集

https://leetcode-cn.com/problems/partition-equal-subset-sum/

一：dp

用dp[i][j] = True表示能用前i个数凑出j，False就是不能。将该题转换为01背包问题，即数组中的数能否凑出sum/2，能则说明存在一种分割方法将数组等分。

i=0表示没有数，因此i=1表示数组0号元素，即dp[i][j]表示能否用数组[0...i-1]凑出

dp[i][j] =  dp[i-1][j]    or    dp[i-1][j-nums[i-1]]
              不用i-1                     用i-1

base case

dp[0][j] = False	#0个数什么也凑不出
dp[i][0] = True		#0一定能凑出

class Solution:
    def canPartition(self, nums) -> bool:
        n =len(nums)
        s = sum(nums)
        if s%2 !=0: return False	#和为奇数说明无法等分
        s = s//2
        dp = [[False]* (s+1) for _ in range(n+1)]
        for i in range(n+1):	#重点：base case
            dp[i][0] = True
        for i in range(1, n+1):
            for j in range(1,s+1):
                if j-nums[i-1] >= 0:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[n][s]