494. 目标和(leetcode)

LXL's Blog / 2024-09-03 / 原文

https://leetcode.cn/problems/target-sum/solutions/2119041/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-s1cx/

灵神的代码实现比我自己写的更好,可以多学习学习
这道题的关键点在于想到正数和+负数和=target,且sum=正数和-负数和,则可推得正数和为多少
这样就可以方便的转化为01背包问题,即在前i个数中选择,体积恰好等于j的(装满背包)的方法种数,f[i][j]=f[i-1][j]+f[i-1][j-nums[i-1] ] ,这里nums[i-1]是因为nums从0开始,而f从1开始,f[1]表示在前1个数中进行选择,其实选择的就是nums[0],因此f和nums下标偏差1

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int s = 0;
        for (int x : nums) {
            s += x;
        }
        s -= Math.abs(target);
        if (s < 0 || s % 2 == 1) {
            return 0;
        }
        int m = s / 2; // 背包容量

        int n = nums.length;
        int[][] f = new int[n + 1][m + 1];
        f[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int c = 0; c <= m; c++) {
                if (c < nums[i]) {
                    f[i + 1][c] = f[i][c]; // 只能不选
                } else {
                    f[i + 1][c] = f[i][c] + f[i][c - nums[i]]; // 不选 + 选
                }
            }
        }
        return f[n][m];
    }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/target-sum/solutions/2119041/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-s1cx/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // 思路:求出加法总和x,x-负数和=target
        // 负数和=sum-x
        // 则x = (sum+target) / 2
        // 题意:即在nums中选出若干数,能够凑出x出来
        // 这样就转化成了01背包了
        // f[i][j]表示在前i个数中选取 体积不超过j的选法,价值等于j的,有多少种方法
        // f[i][j] = f[i-1][j] + f[i-1][j-nums[i]]
        // f[0][0]=1; // 选0个数凑成0也是一种方法
        int[][] f=new int[nums.length+10][1010];
        int sum=0;
        for(int i=0;i<nums.length;i++)sum+=nums[i];
        sum-=Math.abs(target);
        if(sum<0 || sum%2==1)return 0;
        int x=sum >> 1;
    
        f[0][0]=1;
        for(int i=1;i<=nums.length;i++)
            for(int j=0;j<=x;j++)
            {
                // 这里nums[i]需要偏移一位,因为f[1]意味着前一个数中选,第一个数就是nums[0],索引差了1,因此偏移
                if(j>=nums[i-1])f[i][j]=f[i-1][j]+f[i-1][j-nums[i-1]];
                else f[i][j]=f[i-1][j];
            }
        return f[nums.length][x];
    }
}