剑指 Offer II 102. 加减的目标值:从二维偏移 DP 到 01 背包转化的多语言题解
剑指 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 <= 200 <= nums[i] <= 10000 <= 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「分割等和子串」(同为子集和计数)放在一起对比练习。