剑指 Offer II 102. 加减的目标值:从二维偏移 DP 到 01 背包转化的多语言题解

原创2026-10-15 17:12:581,984 阅读
文章标签:教程示例工程教育

剑指 Offer II 102. 加减的目标值:从二维偏移 DP 到 01 背包转化的多语言题解

本篇技术指南围绕《剑指 Offer(专项突击版)》第 102 题「加减的目标值」展开,该题与 LeetCode 主站 494. 目标和 为同一道题。文章完整继承原题解文档的四种解法(偏移量二维 DP、01 背包转化、一维空间优化、记忆化搜索),并结合仓库中的多语言实现源码(Python、Java、C++、Go、Swift)逐层拆解状态定义、转移方程与边界剪枝,读完即可掌握"每个数前添加正负号凑出指定目标值"这一类计数 DP 问题的完整套路。

题目描述与核心约束

给定一个正整数数组 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

示例 2:

输入:nums = [1], target = 1
输出:1

提示(数据范围):

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

从约束可以看到:数组长度最多 20,总和最多 1000,target 落在 [-1000, 1000]。这意味着所有可能的"加减结果"都落在 [-1000, 1000] 区间内,区间宽度为 2001——这正是方法一中使用固定 2001 列 DP 表的直接依据。

方法一:动态规划(带偏移量的二维 DP)

思路要点

每个数前加正号或负号,使结果等于 target。n <= 20 时理论上可以暴力搜索(2^20 ≈ 100 万),但题目明确允许使用计数 DP。前 i 个数能形成的和落在 [-1000, 1000],数组下标不能为负,因此用偏移量 1000 把下标变为非负。

定义 dp[i][j] 表示前 i 个数凑出和 j - 1000 的方案数(即真实和为 j-1000,数组下标为 j)。dp[i][j] 由上一行"加上 nums[i]"或"减去 nums[i]"两个方向累加而来:

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

边界条件:target 超出 [-1000, 1000] 直接返回 0;初始化第一行时,nums[0] 取正、取负各计 1 种方案。

多语言实现

仓库中该方法对应的源码文件为 Solution.py、Solution.java、Solution.go、Solution.swift。

Python3:

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        if target < -1000 or target > 1000:
            return 0
        n = len(nums)
        dp = [[0] * 2001 for i in range(n)]
        dp[0][nums[0] + 1000] += 1
        dp[0][-nums[0] + 1000] += 1
        for i in range(1, n):
            for j in range(-1000, 1001):
                if dp[i - 1][j + 1000] > 0:
                    dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000]
                    dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000]
        return dp[n - 1][target + 1000]

Java:

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        if (target < -1000 || target > 1000) {
            return 0;
        }

        int n = nums.length;
        int[][] dp = new int[n][2001];

        dp[0][nums[0] + 1000] += 1;
        dp[0][-nums[0] + 1000] += 1;

        for (int i = 1; i < n; i++) {
            for (int j = -1000; j <= 1000; j++) {
                if (dp[i - 1][j + 1000] > 0) {
                    dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000];
                    dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000];
                }
            }
        }
        return dp[n - 1][target + 1000];
    }
}

C++:

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int s = 0;
        for (int x : nums) s += x;
        if (s - target < 0 || (s - target) % 2 != 0) return 0;
        target = (s - target) / 2 + 1;
        vector<int> dp(target);
        dp[0] = 1;
        for (int i = 1; i < nums.size() + 1; ++i) {
            for (int j = target - 1; j >= nums[i - 1]; --j) {
                dp[j] += dp[j - nums[i - 1]];
            }
        }
        return dp[target - 1];
    }
};

Go:

func findTargetSumWays(nums []int, target int) int {
	if target < -1000 || target > 1000 {
		return 0
	}
	n := len(nums)
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, 2001)
	}
	dp[0][nums[0]+1000] += 1
	dp[0][-nums[0]+1000] += 1
	for i := 1; i < n; i++ {
		for j := -1000; j <= 1000; j++ {
			if dp[i-1][j+1000] > 0 {
				dp[i][j+nums[i]+1000] += dp[i-1][j+1000]
				dp[i][j-nums[i]+1000] += dp[i-1][j+1000]
			}
		}
	}
	return dp[n-1][target+1000]
}

Swift:

class Solution {
    func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
        if target < -1000 || target > 1000 {
            return 0
        }

        let n = nums.count
        var dp = Array(repeating: Array(repeating: 0, count: 2001), count: n)

        dp[0][nums[0] + 1000] += 1
        dp[0][-nums[0] + 1000] += 1

        for i in 1..<n {
            for j in -1000...1000 {
                if dp[i - 1][j + 1000] > 0 {
                    dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000]
                    dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000]
                }
            }
        }

        return dp[n - 1][target + 1000]
    }
}

复杂度: 时间复杂度 O(n × S),空间复杂度 O(n × S),其中 S 为偏移后的和范围(本题中为 2001 个状态)。

方法二:动态规划(转化为 01 背包计数)

数学转化推导

方法一把和的正负全部展开,状态空间较大。方法二利用代数关系做一次巧妙的转化:

设数组总和为 s,取负号子集的和为 neg,则所有取正号的数之和为 s - neg,整个表达式的结果为:

(s - neg) - neg = s - 2 * neg = target

即:

neg = (s - target) / 2

于是问题转化为:在数组 nums 中选出一个子集,使其元素之和恰好等于 (s - target) / 2,求这样的子集个数——这正是经典的二维 01 背包计数问题。

可行性剪枝: 由于 neg >= 0 且为整数,必须满足 s - target >= 0 且 (s - target) 为偶数,否则直接返回 0。

定义 dp[i][j] 表示前 i 个数中选取若干元素、和为 j 的方案数。对于第 i 个数(下标 i-1)有两种选择:

  • 不选:dp[i][j] += dp[i - 1][j]
  • 选(前提 j >= nums[i-1]):dp[i][j] += dp[i - 1][j - nums[i - 1]]

多语言实现

仓库中该方法对应源码为 Solution2.py、Solution2.java、Solution2.go、Solution2.swift,以及 Solution.cpp(采用一维滚动写法)。

Python3(二维):

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        if s - target < 0 or (s - target) % 2 != 0:
            return 0
        target = (s - target) // 2 + 1
        n = len(nums) + 1
        dp = [[0] * target for _ in range(n)]
        dp[0][0] = 1
        for i in range(1, n):
            for j in range(target):
                dp[i][j] = dp[i - 1][j]
                if nums[i - 1] <= j:
                    dp[i][j] += dp[i - 1][j - nums[i - 1]]
        return dp[-1][-1]

Java(一维滚动):

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

Go(一维滚动):

func findTargetSumWays(nums []int, target int) int {
	s := 0
	for _, x := range nums {
		s += x
	}
	if s-target < 0 || (s-target)%2 != 0 {
		return 0
	}
	target = (s-target)/2 + 1
	dp := make([]int, target)
	dp[0] = 1
	for i := 1; i < len(nums)+1; i++ {
		for j := target - 1; j >= nums[i-1]; j-- {
			dp[j] += dp[j-nums[i-1]]
		}
	}
	return dp[target-1]
}

Swift:

class Solution {
    func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
        let s = nums.reduce(0, +)
        if s - target < 0 || (s - target) % 2 != 0 {
            return 0
        }
        let target = (s - target) / 2
        var dp = Int
        dp[0] = 1

        for num in nums {
            for j in stride(from: target, through: num, by: -1) {
                dp[j] += dp[j - num]
            }
        }
        return dp[target]
    }
}

说明:方法二在 Java / C++ / Go 的仓库实现里直接采用"一维倒序滚动"写法,与二维写法等价但更省空间,详见下文方法三的原理。

方法三:动态规划(一维空间优化)

方法二的背包转移只依赖上一行的状态 dp[i-1][j] 与 dp[i-1][j - nums[i-1]],因此可以用一维数组滚动更新。每个数最多选一次,内层必须倒序更新,否则当前行会覆盖上一行还未使用的状态,导致同一个数被重复选取(退化成完全背包语义)。

仓库中该方法对应源码为 Solution3.py:

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        if s - target < 0 or (s - target) % 2 != 0:
            return 0
        target = (s - target) // 2 + 1
        n = len(nums) + 1
        dp = [0] * target
        dp[0] = 1
        for i in range(1, n):
            for j in range(target - 1, nums[i - 1] - 1, -1):
                dp[j] += dp[j - nums[i - 1]]
        return dp[-1]

关键点:内层循环 j 从大到小遍历,且下界为 nums[i-1](容量不足时无法选取当前数)。这样每个物品只被考虑一次,空间复杂度由 O(m × n) 降为 O(n)。

方法四:记忆化搜索

方法三仍属于递推形式。方法四回归问题本源:枚举每个数取正号或取负号,并用缓存记忆化搜索剩余目标和,实现与转移逻辑最贴近题意,代码也最直观。

仓库中该方法对应源码为 Solution4.py:

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        @cache
        def dfs(i, t):
            if i == n:
                if t == target:
                    return 1
                return 0
            return dfs(i + 1, t + nums[i]) + dfs(i + 1, t - nums[i])

        ans, n = 0, len(nums)
        return dfs(0, 0)
  • 递归出口:遍历完所有数(i == n)时,若当前累计和 t 等于 target 则返回 1,否则返回 0;
  • 状态转移:对第 i 个数做两种选择——dfs(i + 1, t + nums[i])(取正)与 dfs(i + 1, t - nums[i])(取负),二者相加;
  • 使用 @cache 记忆化 (i, t) 状态,避免大量重复子问题(例如前若干个数累计和相同的分支会被合并)。

四种解法复杂度与适用场景对比

解法 核心思想 时间复杂度 空间复杂度 适合场景
方法一:偏移量二维 DP 用 j + 1000 映射负数下标,直接枚举加减 O(n × 2001) O(n × 2001) 数据范围明确(本题和最大 1000)时最稳妥
方法二:转化 01 背包 由 s - 2*neg = target 转为子集计数 O(n × (s-target)/2) O(n × (s-target)/2) 需要对"取负"语义做代数抽象理解的场景
方法三:一维滚动背包 倒序更新一维数组 O(n × (s-target)/2) O((s-target)/2) 容量维远小于 2001 时更省空间
方法四:记忆化搜索 枚举取正/取负 + 缓存 O(n × 状态数) O(n × 状态数) 代码最贴近题意,便于口述与面试讲解

与仓库源码的对照阅读指引

  • 本题题解主文档:剑指 Offer II 102. 加减的目标值/README.md,完整包含四种方法的多语言代码;
  • 方法一源码:Solution.py、Solution.java、Solution.go、Solution.swift;
  • 方法二源码:Solution2.py、Solution2.java、Solution2.go、Solution2.swift,以及采用一维写法的 Solution.cpp;
  • 方法三源码:Solution3.py;
  • 方法四源码:Solution4.py;
  • 主站同题:494. Target Sum/README.md,其题解从 s >= target 且 (s-target) 为偶数的剪枝条件出发,完整推导了 f[i][j] = f[i-1][j] + f[i-1][j-nums[i-1]] 的背包转移方程,可与本文方法二相互印证。

实践建议: 面试中推荐按"方法四 → 方法二 → 方法三"的顺序讲解——先用记忆化搜索讲清朴素思路,再用代数转化把问题化为 01 背包计数,最后以倒序一维滚动收尾展示优化能力。刷题时则可将本题作为"符号分配类 DP"的模板题,与主站 494 题、剑指 Offer II 101「分割等和子串」(同为子集和计数)放在一起对比练习。

登录后查看全文
leetcode