[LeetCode416. Partition Equal Subset Sum]
给定一个非负数组，是否可以将其分成两个和相等的子数组。
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
动态规划
首先，如果数组和为奇数，显然不可对半分。
其次，我们定义一个大小为（数组和sum+1）的数组dp，dp的每个元素记录当前位置index是否可以由nums中的数相加得到。
最后，我们只需要判断dp[sum // 2]是否为True,即可判断是否可以对半分。
class Solution:
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
sum_all = sum(nums)
if sum_all % 2:
return False
target = sum_all // 2
dp = [0 for i in range(sum_all + 1)]
dp[0] = 1
for num in nums:
for i in range(target, -1, -1):
if dp[i]:
dp[i + num] = 1
if dp[target] == 1:
return True
return False
[LeetCode494. Target Sum]
给定一个非负数组a和一个目标值s，你可以使用+、-两种符号添加到a的每个元素中，求解有多少种方法得到s。
Example:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
动态规划
考虑一种简单情况，和为s的情况是否存在，而不必计较其情况的个数。
我们定义集合Vi来保存使用前i个数字能得到的所有和的情况，遍历整个数组一次，最后检查s是否在集合V中即可判断。而关键是集合Vi的更新，对于新加入的数nums[i], 在原来集合V{i-1}上将其加上或者减去，即可以得到：
Vi = (V_{i-1} + num[i]) U (V_{i-1} - num[i])
所以在当前问题中，可以定义一个数组dp[i][j]用作记录前i个数有多少种方法可以得到和j。
此时i的维度为（len(nums) + 1），j的维度为（2 * sum(a) + 1）。（因为j的范围为（-sum(a) ~ sum(a)））.
dp初始化为：dp[0][sum(a) + 1] = 0。
dp更新规则为：
dp[i + 1][j] = dp[i][j - nums[i]] + dp[i][j + nums[i]]
dp[i+1]由它左右两肩上距离为nums[i]的数相加得到。
具体如图：
算法实现
class Solution:
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
n = len(nums)
sum_all = sum(nums)
sum_tmp = 0
dp = [[0 for _ in range(2*sum_all + 1)] for _ in range(n+1)]
dp[0][sum_all] = 1
for i, num in enumerate(nums):
sum_tmp += num
for j in range(sum_all - sum_tmp, sum_all + sum_tmp + 1):
if j - num >= 0:
dp[i + 1][j] += dp[i][j - num]
if j + num <= 2 * sum_all:
dp[i + 1][j] += dp[i][j + num]
return dp[n][sum_all+S]
改进方法
由于dp[i+1][j]由dp[i][j]更新之后，dp[i][j]不再被使用，所以可以使用一维数组替代原来的二维数组。
class Solution:
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
n = len(nums)
sum_all = sum(nums)
if sum_all < S:
return 0
dp = [0 for _ in range(2*sum_all + 1)]
dp[sum_all] = 1
for num in nums:
dp_new = [0 for _ in range(2*sum_all + 1)]
for j in range(num, 2 * sum_all + 1 - num):
if dp[j]:
dp_new[j-num] += dp[j]
dp_new[j+num] += dp[j]
dp = dp_new
return dp[sum_all+S]
动态构造字典
一种interesting的方法，把dp数组转化为对应的字典，key为sum值，value为可能的情况个数。
from collections import Counter
class Solution:
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
dp = {0:1}
for num in nums:
dp_new = Counter()
for old in dp:
dp_new[old + num] += dp[old]
dp_new[old - num] += dp[old]
dp = dp_new
return dp[S]
深度优先（DFS）
这种方法思路比较直接，树深为nums的长度，下一次搜索的值是(s - cur_num) 和 (s + cur_num)。只是测试超时。
class Solution:
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
sum_all = sum(nums)
if sum_all < S:
return 0
self.result = 0
self.dfs(nums, 0, S)
return self.result
def dfs(self, nums, d, S):
if d == len(nums):
if S == 0:
self.result += 1
return
if d < len(nums):
self.dfs(nums, d+1, S + nums[d])
self.dfs(nums, d+1, S - nums[d])
Reference
- 花花酱 LeetCode 494
更多精彩文章，欢迎关注公众号“Li的白日呓语”。