問題描述
這題的最優解是使用Bottom up DP, 題目描述和詳細解法可以參考這篇文章. 本文示範一下這題也可以直接使用這篇文章總結的0-1背包問題2維dp模版一字不改直接解
0-1背包問題2維度dp模版解法
問題稍微轉換一下就可以等價成為0-1背包問題:
如果nums的和為奇數, 直接返回False, 因為不可能分成等和的兩半加起來還是奇數.
有N個物品, 每個物品Cost為nums[i]
, Value為nums[i]
, 其中 i 屬於 [0, …, N-1]
有一個書包, 容量為sum(nums) / 2
求書包能裝下的最大Value 是否就是sum(nums) / 2
Python 2 代碼實現如下
class Solution(object): def maxKnapsackValue(self, N, C, W, V): # init dp row = [0] * (1 + V) dp = [] for i in range(N + 1): dp.append(list(row)) for i in range(1, N + 1): for v in range(1, V + 1): dp[i][v] = dp[i - 1][v] if v - C[i - 1] >= 0: dp[i][v] = max( dp[i][v], dp[i - 1][v - C[i - 1]] + W[i - 1] ) return dp[N][V] def canPartition(self, nums): """ :type nums: List[int] :rtype: bool """ isum = sum(nums) if isum % 2 != 0: return False target = isum / 2 print target n = len(nums) return self.maxKnapsackValue( n, nums, nums, target) == target
該解法能過OJ, 雖然時間和空間用的都比較多.