动态规划应用的另一个算法题：Target Sum
LeetCode有一道算法题：Target Sum
给出一个int数组和int值S，可以任意使用“+”或者“-”运算符把int数组的所有元素计算出来，让其结果等于这个S，问可以达到这样效果的计算方法有多少种？
比如，一个int数组[1,1,1,1,1,]，另外一个S值为3，那么有以下几种方式可以实现数组元素的最终值等于S：
-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种。
我们先分析这个题目，既然是算最优解，那么只需要符合递推规则就可以使用动态规划处理。
那么它是否实现了递推要求，每一项的计算依赖于前面一项的计算结果，并且每一项的计算都是最优解。
如上面的例子，我们可以这样设想，要求int数组5个元素的计算结果等于S的最多方法数，那么我们可以从最后一个元素开始分析，最多方法数就是int数组的元素计算是减去最后一个元素等于S的方法数再加上int数组的元素计算是加上最后一个元素等于S的方法数，要么减，要么加，所以涵盖了所有情况。
所以减去最后元素的就会依赖前面4个元素的计算结果等于S+1的方法数，而加上最后元素的就会依赖前面4个元素的计算结果等于S-1的方法数，以此类推，前面4个元素的计算依赖于前面3个元素，前面3个元素的计算依赖于前面2个元素......
所以这道题也符合递推的规则，接下来我们就通过动态规划去实现这个算法题。
我们假如int数组的累加和是P，累减和是R，数组的总和是sum，目标结果是S，那么就有：
P - R = S 我们可以这样转换：
//左右两边同时加上R和PP - R + R + P = S + R + P2P = S + sumP = (S + sum)/2
累加和可以通过目标结果加上数组的总和再除于2可得，所以如果不能整除2就代表这个int数组的元素无论怎么计算都不等于S，并且也要判断sum是否小于S，数组的总和也小于目标结果，肯定也是无解的，代码实现如何：
int sum=0;//计算数组元素的总和sumfor(int i=0;i<nums.length;i++){sum += nums[i];}//判断S是否大于sum或者S+sum的和是否可以整除2if(S>sum||(S+sum)%2==1){return 0;}
然后开始我们动态规划的数组定义，定义如下：
//s是累加数，n是int数组的长度int[][] dp=new int[n+1][s+1];
这个数组的一维元素代表int数组的前几个元素，二维元素代表int数组的前几个元素的累加和，数组的元素就是代表有多少中方法数。
比如dp[3][2]值，就是代表int数组的前3个元素的累加和等于2的方法数。
接下来我们再进行动态规划数组的边界初始化：
dp[0][0] = 1; 表示用int数组的0个元素累加和等于0的方法数，由于int数组都没有元素进行累加，所以累加和铁定是等于0的，所以方法数也就是1。
为什么不考虑dp[0][j]和dp[i][0]的边界情况？
首先说一下dp[0][j]，除了dp[0][0]等于1，其他j>=1的情况都是等于0，因为累加和固定是0，肯定和j是不相等的，所以它和int数组初始化的默认值0是一样的，就不需要做多余的处理了；然后dp[i][0]，同样除了dp[0][0]等于1，其他i >=1的情况都是不确定的，边界情况处理是要满足可以忽略数组的元素值就可以获取到值，这里dp[i][0]等于多少，还要看数组是否有0的元素，所以不能忽略，就不需要处理这种边界情况。
然后我们开始分析动态规划的方程式。
比如要求dp[i][j]，经过前面的分析，我们可以考虑两种场景：
int数组的前i-1项的累加和再减去第i个元素等于j，这种情况就是不考虑第i个元素在累加和里面，所以累加和只需要考虑前i-1项，用dp表示就是dp[i-1][j];
int数组的前i-1项的累加和再加上第i个元素等于j，这种情况就是考虑第i个元素在累加和里面，所以累加和就是前i-1项的累加和再加上第i个元素等于j，这个等式反回来就是前i-1项的累加和等于j减去第i个元素，用dp表示就是dp[i-1][j-nums[i]。
代码实现如下：
//前面分析i=0的时候除了j=0是等于1，其余都和数组初始化的默认值0一样//所以这里可以直接从i=1开始循环for(int i=1; i < n+1; i++) {for (int j = 0; j < s + 1; j++) {//这里判断a[i-1]是否大于j，如果大于j//那么累加和肯定不能包含a[i-1]这个元素//如果包含了，肯定大于j了if (a[i - 1] <= j) {//累加和考虑a[i-1]这元素dp[i][j] = dp[i-1][j - a[i-1]]+dp[i-1][j];}else{//累加和排除a[i-1]这个元素dp[i][j]=dp[i-1][j];}}}
注意，由于这个算法题给出了int数组都是非负整数，所以累加和肯定也是非负整数，不用考虑累加和是一个负数，然后加上一个大于j的数组元素等于j的这种情况。
最后返回结果：
return dp[n][s]; 以上就是动态规划的算法答案。
但是这个算法还可以优先一下内存空间，我们定义了一个二维数组，在循环计算的时候，每一行的计算都只是依赖于前面一行的数据，一旦计算完了，依赖的这一行数据就再也用不上了，但是却一直占着空间，如下图：
假如要求dp[i][j]，我们需要获取dp[i-1][j]的值，也就是上面的绿色区域，还要判断a[i-1]是否大于j的情况，如果大于，则由上面的分析，直接把dp[i-1][j]的值赋值给dp[i][j]，如果小于，则还要加上dp[i][j-a[i-1]的值，我们由前面的方程式中的代码：
dp[i][j] = dp[i-1][j - a[i-1]]+dp[i-1][j]; 可以知道，dp[i-1][j-a[i-1]]中的j-a[i-1]肯定不比dp[i-1][j]的j要大，所以dp[i-1][j-a[i-1]]的位置只能是上图的有色区域，也就是只能是dp[i-1][j]的区域或者这个区域往左的区域，而绝不会出现在往右的区域。
接下来我们用一个一维数组去实现这个算法：
//以累加数+1作为数组长度int[] dp = new int[s+1];
这个一维数组定义了之后代表用int数组的0个元素累加和等于dp角标的方法数数组集合，前面我们分析，只有dp[0][0]才可以直接获取边界情况结果，所以这里dp[0]=1，代表int数组的0个元素累加和等于0的方法数。
由前面的分析，一维数组的动态规划方程式就是这样：
//当j大于等于a[i]时就会加上a[i]到累加和//然后加上原来的d[j]赋于新值dp[j] = dp[j - a[i]] + dp[j];//如果小于则不加锁a[i]到累加和//就是还是把原来的值重新赋值了一次，所以这个可以不写，只需要处理上面的情况即可dp[j] = dp[j]
所以最终代码实现如下：
for(int i = 1; i < n+1; i++) {for (int j = s; j >= a[i-1]; j--) {dp[j] = dp[j - a[i-1]] + dp[j];}}//返回最终结果return dp[s]
可能有人会有疑问，为什么第二for循环要从最大开始递减遍历？
我们先看图：
假如要求dp[j]，则要获取原来的dp[j]值，并且如果j>=a[i-1]，则还要加上dp[j-a[i-1]]值，dp[j-a[i-1]]前面分析过，只可能出来在dp[j]或者dp[j]往左的位置，计算之后把dp[j]旧值覆盖，如果是j<a[i-1]则不需要覆盖，因为值并没有发生变化，注意，dp[j]往左的元素还是原来的数据，并没有覆盖。
然后j开始递减来到最后的第二位：
同样的，如果j>=a[i-1]，则用新值覆盖旧值，如此反复，就完成了最终结果计算。
从最大开始递减循环，可以保证数据的完整性，每次计算用的都是之前计算行数据的旧数据，不会发生计算同一行数据的时候，某个新值覆盖完了，下一个新值可能会使用到前面覆盖的新值。
我们现在看看用递增循环会怎么样：
for(int i = 1; i < n+1; i++) {for (int j = a[i-1]; j <= s; j++) {dp[j] = dp[j - a[i-1]] + dp[j];}}
比如a[i-1]=1，也就是j=1，如下图：
dp[j] = dp[j-a[i-1]]+dp[j]，也就是dp[1]=dp[0]+dp[1]，这时候会把dp[1]赋值新值。
然后j递增，也就是j=2，那么dp[j] = dp[j-a[i-1]]+dp[j]也就是dp[2]=dp[1]+dp[2]，这时候dp[1]已经是新值了，所以这样的计算结果是错误的，因此需要从最大递减循环才能保证数据的正确性。
动态规划的实现又很多空间问题都可以优化，最好可以画图去分析怎么优化才是最好最准确的。