// @Title: 目标和 (Target Sum)
// @Author: qisiii
// @Date: 2024-09-25 19:42:11
// @Runtime: 638 ms
// @Memory: 40.2 MB
// @comment: 回溯
// @flag: BLUE
class Solution {
    int count = 0;

    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums, 0, target, 0);
        return count;
    }

    private void dfs(int[] nums, int cur, int target, int sum) {
        if (cur == nums.length) {
            if (sum == target) {
                count++;
            }
            return;
        }
        dfs(nums, cur + 1, target, sum + nums[cur]);
        dfs(nums, cur + 1, target, sum - nums[cur]);
    }
}

// @Title: 目标和 (Target Sum)
// @Author: qisiii
// @Date: 2024-09-25 19:09:48
// @Runtime: 3 ms
// @Memory: 42.4 MB
// @comment: 动规+一堆细节，这个题完全没有解出来的快乐感
// @flag: GREEN
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for(int i:nums){
            sum+=i;
        }
        //如[1] 2这种状况
        if(sum<target){
            return 0;
        }
        //即得不到一个合理的结果值
        if((sum+target)%2!=0){
            return 0;
        }
        target=(sum+target)/2;
        if(target<0){
            return 0;
        }
        int[][] dp=new int[nums.length][target+1];
        for(int j=0;j<=target;j++){
            if(nums[0]==j){
                dp[0][j]=1;
            }
        }
        int zeroNum=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==0){
                zeroNum++;
            }
            dp[i][0]=(int)Math.pow(2,zeroNum);
        }
        for(int i=1;i<nums.length;i++){
            for(int j=1;j<=target;j++){
                if(j<nums[i]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];
                }
            }
        }
        return dp[nums.length-1][target];
    }
}