416. 分割等和子集 - 力扣（LeetCode）?

解1：二維dp數組，時間O(m*n)，空間O(m*n)，m、n為dp數組的行和列數。

判斷原數組總和能否整除2；

將target設為total // 2（若是total / 2，target為float，需要轉為int才能以target為維度新建dp數組）；

* 新建dp，行數 = nums長度，列數 = target+1，i行j列dp[i][j]表示從子數組nums[0:i+1]（第0~第i個數）不重復地取數，能夠獲得的不超過j的最大總和。dp[len(nums)-1][target]若等于target，說明在整個nums中能夠不重復地取出總和恰好為target的數，返回true。

* 考慮dp[i][j]的計算：若當前數nums[i] > j，說明i不可加入，于是dp[i][j] = dp[i-1][j]。否則，i可能加入，獲得總和 = dp[i-1][j-nums[i]] + nums[i]（將加入了i數的背包想象成兩部分，一部分是i數本身，價值和重量都為i，另一部分不含i而且重量上限為j-nums[i]，dp[i-1][j-nums[i]]就是第二部分能取到的最大價值）；i也可以選擇不加入，獲得總和 =?dp[i-1][j]。用i加入/不加入中的較大者更新dp[i][j]。

由此可見，需要通過dp[i][j]左側及上側的值計算它。遍歷時從左到右，從上到下。

* base情況，考慮左、上邊緣的值：1）dp[x][0]表示總和上限=0，因此dp[x][j]=0（dp本來都初始化為0，不需處理）；2）dp[0][x]表示只考慮nums第0個數，則當x小于nums[0]，初始為0，當x不小于nums[0]，都初始化為nums[0]。

遍歷每行、每列，直到右下角。

class Solution:def canPartition(self, nums: List[int]) -> bool:if len(nums) <= 1:return Falsetotal = sum(nums)if total % 2 != 0:return Falsetarget = total // 2#dp[i][j]:從nums的[0, i]中取數，能獲得的不超過j的最大總和.dp: len(nums) * (target+1)dp = [[0 for _ in range(target+1)] for _ in range(len(nums))]#轉移：dp[i][j] = max(dp[i-1][j], dp[i][j-nums[i]]+nums[i])#base：不超過0的最大總和：只能不取任何數，dp[x][0] = 0, #      只考慮第0個數時：dp[0][x] = nums[0] if x >= nums[0] else = 0for x in range(nums[0], target+1):dp[0][x] = nums[0]for j in range(1, target+1):#最大和=jfor i in range(1, len(nums)):#取0~i個數if nums[i] > j:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])return dp[-1][-1] == target

解2：壓縮為一維dp數組，時間O(m*n)，空間O(n)

將物品/nums[i]維度壓縮掉了，dp是長度=target+1的一維數組，按nums[0]的情況初始化dp。由于新的dp[j]需要參考“上一行左側”或“上一行正上方”的值，應該從后往前遍歷dp，防止上一行的值在使用之前被新的值覆蓋。若當前數nums[i]超過當前上限j，不改變dp[j]的值（相等于沿用上一行正上方的值）；否則，用當前值dp[j]與dp[j-nums[i]] + nums[i]的較大者更新當前值。

class Solution:def canPartition(self, nums: List[int]) -> bool:if len(nums) <= 1:return Falsetotal = sum(nums)if total % 2 != 0:return Falsetarget = total // 2dp = [0 for _ in range(target+1)]for i in range(1, target+1):if nums[0] <= i:dp[i] = nums[0]for i in range(1, len(nums)):for j in range(target, 0, -1):if nums[i] <= j:dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])return dp[-1] == target