LeetCode494. 目标和

前言

本题就是找到两个集合，使左边的集合减去右边的集合的值为target

即left-right=target；并且right=sum-left；

所以left=(sum+target)/2；如果(sum+target)/2有余数，则返回0。

思路

1.确定dp数组的含义

dp数组含义：dp[j]:表示当背包容量为j时，一共有dp[j]种方法得到target。

2.递推公式

dp[j]+=dp[j-nums[i]];

因为要求的是一共有多少种方式，就是当nums下标为0时的个数下标为1时的个数，以此类推。

此处的递推公式和之前的不一样，以后用动态规划解决组合问题的时候都会使用该递推公式。

3.dp数组初始化

dp[0]=1;根据定义就可以知道，当和为0时，只有一种方式就是一个也不选。

4.dp数组的遍历顺序

根据递推公式就可以知道是按照正序遍历的，不过在内部循环时还是要倒序，防止重复获取元素。

5.打印dp数组

dp数组的最后一个元素就是最后的结果一共有多少种方式

代码

class Solution {    public int findTargetSumWays(int[] nums, int target) { int sum = 0; int length = nums.length; for(int i = 0;i<nums.length;i++){     sum+=nums[i]; } if((sum+target)%2!=0){     return 0;   } int left = (sum+target)/2; if(left<0){     return 0; } int dp[] = new int[left+1]; dp[0] = 1; for(int i =0;i=nums[i];j--){  dp[j]+=dp[j-nums[i]];     } }    return dp[left];    }}