LeetCode_494_目标和

题目链接

• https://leetcode.cn/problems/target-sum/

题目描述

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

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

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

示例 1：

输入：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
1
2
3
4
5
6
7
8

示例 2：

输入：nums = [1], target = 1
输出：1
1
2

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

解题思路

动态规划

• 将这些数分为两堆，+号为left，-号为right。然后相加和为target，也就是left + right = target
• 此外left - right = sum,可以得到left = (sum + target) / 2
• 对于一个固定数组来说，sum和target都是确定的，所以left可以求出来，此时问题就转换为在集合nums中找出和为left的组合，也就是装满容量为left的背包有几种方法

动态规划五部曲

• 确定dp数组以及下标的含义
  • dp[j]:装满j容量的背包，有dp[j]种方法
• 确定递推公式
  • 在不考虑nums[i]的情况下，装满容量为j - nums[i]的背包，有dp[j- nums[i]]种方法
  • 因此dp[j] += dp[j - nums[i]]
• dp数组初始化
  • dp[0] = 1，也就是装满容量为0的背包，有1种方法：就是装0个东西
• 确定遍历顺序
  • 01背包问题种，nums放在外循环，且是正序。target放在内循环，且为倒序

AC代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        if ((target + sum) % 2 != 0) {
            return 0;
        }
        int bagWeight = (sum + target) / 2;
        if (bagWeight < 0) {
            bagWeight = -bagWeight;
        }
        int[] dp = new int[bagWeight + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = bagWeight; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagWeight];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23