416. 分割等和子集问题（动态规划）

题目

题解

class Solution:def canPartition(self, nums: List[int]) -> bool:# badcaseif not nums:return True# 不能被2整除if sum(nums) % 2 != 0:return False# 状态定义：dp[i][j]表示当背包容量为j，用前i个物品是否正好可以将背包填满，True/Falsedp = [[False for j in range(sum(nums)+1)] for i in range(len(nums)+1)]for i in range(len(nums) + 1):dp[i][0] = True# 状态转移for i in range(1, len(nums) + 1):for j in range(1, sum(nums) + 1):if j - nums[i-1] >= 0:# 选择用第i个物品或者不用dp[i][j] = dp[i - 1][j - nums[i-1]] or dp[i-1][j]else:dp[i][j] = dp[i-1][j]return dp[len(nums)][int(sum(nums) / 2)]