题解 | #目标和#

题意整理

给定一个整数数组nums和一个整数target。
返回该数组能构成多少种不同的表达式等于target。

方法一（动态规划）

1.解题思路

本题可以转化为一个0-1背包问题。我们将前面添加号的分为一组，记其累加和为a，将前面添减号的分为一组，记其累加和为b。如果能构成一个表达式，使得结果为target，则有 $a + b = s u m, a - b = t a r g e t$ ，其中sum为数组中所有数字的累加和。继续化简一下，可以得到： $a = (s u m + t a r g e t) / 2$ 。如果数组中存在若干数字之和等于a，则对应其中一个合法的表达式等于target。要想a存在， $s u m + t a r g e t$ 必为偶数。

状态定义： $d p [i] [j]$ 表示i个元素时，有多少种不同的组合，其累加和为j。
状态初始化：初始化组成0的情况数为1。
状态转移：遍历nums数组中每一个数字，默认不选当前数字，即 $d p [i + 1] [j] = d p [i] [j]$ 。如果j大于当前数字，则需要加上 $j - n u m s [i]$ 时的组合数，即 $d p [i + 1] [j] + = d p [i] [j - n u m s [i]]$ 。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int findTargetSumWays (int[] nums, int target) {
        //边界情况判断
        int n=nums.length;
        if(n==0) return 0;
        //记录累加和
        int sum=0;
        //遍历nums数组
        for(int num:nums){
            sum+=num;
        }
        //计算背包容量
        int V=(sum+target)/2;
        //如果为奇数，说明nums数组中找不打和为(sum+target)/2的若干数字
        if((sum+target)%2==1) return 0;
        
        //dp[i][j]表示i个元素时，有多少种不同的组合，其累加和为j
        int[][] dp=new int[n+1][V+1];
        //初始化
        dp[0][0]=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<=V;j++){
                //默认不选当前数字
                dp[i+1][j]=dp[i][j];
                //如果选择当前数字，则需要加上j-nums[i]时的组合数
                if(j>=nums[i]){
                    dp[i+1][j]+=dp[i][j-nums[i]];
                }
            }
        }
        return dp[n][V];
    }
}

3.复杂度分析

时间复杂度：总共两次循环，需要执行 $n * (V + 1)$ 次，所以时间复杂度是 $O (n * V)$ 。
空间复杂度：需要额外大小为 $(n + 1) * (V + 1)$ 的dp数组，所以空间复杂度为 $O (n * V)$ 。

方法二（空间优化）

1.解题思路

由于方法一中，每次状态转移，只与上一行的状态有关，所以可以只使用一个维度构建dp数组。每个数字只能选一次，所以需要倒序遍历背包容量，避免重复计算。

图解展示： alt

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int findTargetSumWays (int[] nums, int target) {
        //边界情况判断
        int n=nums.length;
        if(n==0) return 0;
        //记录累加和
        int sum=0;
        //遍历nums数组
        for(int num:nums){
            sum+=num;
        }
        //计算背包容量
        int V=(sum+target)/2;
        //如果为奇数，说明nums数组中找不打和为(sum+target)/2的若干数字
        if((sum+target)%2==1) return 0;
        
        //dp[j]表示有多少种不同的组合，其累加和为j
        int[] dp=new int[V+1];
        //初始化
        dp[0]=1;
        for(int i=0;i<nums.length;i++){
            //每个数字只选一次，所以需要倒序遍历，避免重复
            for(int j=V;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[V];
    }
}

3.复杂度分析

时间复杂度：总共两次循环，需要执行 $n * (V + 1)$ 次，所以时间复杂度是 $O (n * V)$ 。
空间复杂度：需要额外大小为 $V + 1$ 的dp数组，所以空间复杂度为 $O (V)$ 。