49/300
目标和 给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 示例 1: 输入: nums: [1, 1, 1, 1, 1], S: 3 输出: 5 解释: -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 一共有5种方法让最终目标和为3。 注意: 数组的长度不会超过20，并且数组中的值全为正数。 初始的数组的和不会超过1000。 保证返回的最终结果为32位整数。动态规划类型，第六道： 暴力全算，O(2n)，然后数目标和有几个。 动态规划pass 下面这种方法算是暴力的优化，{result: frequency}, 也就是说遇到重复的值，直接合并，加频次。然后提取目标和的频次就好。
举例 [1,1,1]，画个丑图，配合代码食用：
python 字典查找指定键值的两种办法 快速上手defaultdict 避免KeyError collections.defaultdict() dict.get(key, default=None)
class Solution: def findTargetSumWays(self, nums, S): #initialize {0:1} mydict = collections.defaultdict(int) mydict[0] = 1 for num in nums: #initialize {} innerdict = collections.defaultdict(int) for prev_sum in mydict: #add positive innerdict[prev_sum+num] += mydict[prev_sum] #add negative innerdict[prev_sum-num] += mydict[prev_sum] #prepare for the next mydict = innerdict return mydict[S]