0/1背包问题之目标和

题目描述如下:

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个表达式：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 – 1 = 3

解题思路:

刚开始看,觉得没有什么想法,感觉和0/1背包不太相关,想着爆搜回溯法解决.但是看了相关做法后提示可能超时.关于这道题,有两种解法,有的从数学公式的角度推导,比如代码随想录中给出的解法( x – (sum – x) = S),但是感觉难以短时间内想到.看到了这样一种解法:

从上往下推导,宫水三叶的代码太过简单,表示看不懂…..自己理解如下:

这道题可以理解为背包容量为sum的背包,一共有几种装满的方式,和上一篇的0/1背包的方式不同,这个是求组合数.

首先dp数组的定义,毫无疑问是dp[i][j代表使用了i个元素所能组成的和为j的总组合数.那么由于元素可以添加正负号,那么就导致可能出现负数,所以初始化的时候dp[nums.length+1][2*sum+1].至于这里行数为什么加一呢,是为了初始化dp[0][sum]=1.而后,从图中不难看出,对于当前的数字,要不就是加一,得到一个dp,要不就是减一得到一个dp.

1.没有任何数字凑出结果0的方式有1种，这是一种额外的情况，以这个为基础
2.当拿到一个数字1的时候，在上一层的结果0的基础上可以加1也可以减1，那么就到达-1和1的方法就各为1种
3.当额外拿到一个数字2的时候，在原来数字1的结果-1和1的基础上，都可以进行+2和减2操作，那么此时可以得到的结果为-3、-1、1、3
4.在上一轮的结果上，继续加减1操作，如果有结果重合的部分，说明可以有不同的路径可以到达，此时结果应进行叠加
5.继续循环处理上面的操作

6.递推公式:

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

7.代码如下:(在代码中采用了从上往下的遍历顺序)

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        int[][] dp = new int[nums.length+1][2 * sum + 1];
        dp[0][sum] = 1;
        if (target>sum || target < -sum){
            return 0;
        }
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < dp[0].length; j++){
                if(dp[i][j] != 0){
                    dp[i+1][j+nums[i]] += dp[i][j] ;
                    dp[i+1][j-nums[i]] += dp[i][j];
                }
            }
        }
        // for(int i = 0; i < dp.length; i++){
        //     for(int j = 0; j <dp[0].length; j++){
        //         System.out.print(dp[i][j]);
        //     }
        //     System.out.println();
        // }
        return dp[dp.length-1][sum + target];
    } 
}

另一种更简单的一维dp如下:

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

关于这个递推公式的理解:

在例如里面讲到了,求dp[5]就是把所有的dp[j-nums[i]]加起来,那么就是dp[0]+dp[1]+dp[2]+dp[3]+dp[4]+dp[5]那么怎么实现这样相加的呢?在外层循环中是遍历每个nums[i],而在内侧循环中,倒序遍历每个背包容量(j),对于一个j而言,他每次从外层循环到内层都经历了不同的i,也就是说dp[j]+dp[j-nums[i]],而后面这个dp[j-nums[i]]相当于dp[0],dp[1],dp[2],dp[3],dp[4],dp[5]所以这样累加起来,正好完成了目的.

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/88863.html

0/1背包问题之目标和

相关推荐