[数据结构与算法]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.length;i++){
            for(int j = left;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
    return dp[left];
    }
}