力扣链接：494. 目标和，难度：中等。
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1:
输入: nums = [1,1,1,1,1], target = 3
输出: 5
解释:
-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
思路
如果你以前没有解决过类似的问题，那么这个问题相当难。所以在开始做这道题之前，建议你先做另一道与这道题类似的相对简单的题目416. 分割相等子集和。
- 当我们看到一组数字被使用一次通过某种计算得到另一个数字（就像这道题一样）时，我们可以认为这是一个
0/1背包问题。 0/1背包问题属于动态规划。动态规划意味着当前问题的答案可以从上一个类似的问题中推导出来。因此，dp数组用于记录所有答案。0/1背包问题的核心逻辑是使用二维dp数组或者一维dp滚动数组，先遍历物品，再遍历背包大小（逆序 或者 使用dp.clone），然后引用当前'物品'大小对应的前一个值。- 使用二维
dp数组需要记住的东西很多，面试的时候很难一次性写对，这里就不描述了。
“动态规划”的模式
“动态规划”分为五步
- 确定数组
dp的每个值代表的含义。 - 初始化数组
dp的值。 - 根据一个示例，“按顺序”填入
dp网格数据。 - 根据
dp网格数据，推导出“递推公式”。 - 写出程序，并打印
dp数组，不合预期就调整。
细说这五步
- 确定数组
dp的每个值代表的含义。- 先确定
dp是一维数组还是二维数组。“一维滚动数组”意味着每次迭代时都会覆盖数组的值。大多时候，用“一维滚动数组”代替“二维数组”可以简化代码；但有些题目，比如要操作“两个对等数组”，为了理解方便，还是使用“二维数组”。 - 尝试使用问题所求的
返回值的含义作为dp[i]（一维）或dp[i][j]（二维）的含义，约60%的概率能行。如果不行，再尝试其他含义。 - 设计上尽量考虑保存更丰富的信息，重复信息只在某个
dp[i]中保存一次就够了。 - 使用简化的含义。如果用
布尔值可以解决问题，就不要用数值。
- 先确定
- 初始化数组
dp的值。dp的值涉及两个层面：dp的长度。通常是：条件数组长度加1或条件数组长度。dp[i]或dp[i][j]的值。dp[0]或dp[0][0]有时需要特殊处理。
- 根据一个示例，“按顺序”填入
dp网格数据。- “递推公式”是“动态规划”算法的核心。但“递推公式”是隐晦的，想得到它，就需要制表，用数据启发自己。
- 如果原示例不够好，需要自己重新设计一个。
- 根据示例，填入
dp网格数据，需要“按顺序”填，这是很重要的，因为它决定了代码的遍历顺序。 - 大多时候，从左到右，从上到下。但有时需要从右向左、由下而上、从中间向右（或左），如“回文串”问题。有时，还需要一行遍历两次，先正向，再反向。
- 当顺序决定对了，起点就决定好了，从起点出发，“按顺序”填写
dp网格数据，这也是在模拟程序处理的过程。 - 在此过程中，您将获得写出“递推公式”的灵感。如果您已经能推导出公式，不需要填完网格。
- 根据
dp网格数据，推导出“递推公式”。- 有三个特别的位置需要注意：
dp[i - 1][j - 1]、dp[i - 1][j]和dp[i][j - 1]，当前的dp[i][j]往往取决于它们。 - 操作“两个对等数组”时，因为对称性，我们可能需要同时使用
dp[i - 1][j]和dp[i][j - 1]。
- 有三个特别的位置需要注意：
- 写出程序，并打印
dp数组，不合预期就调整。- 重点分析那些不合预期的数值。
读完了上面的内容，是不是感觉“动态规划”也没有那么难了？试着解出这道题吧。🤗
步骤
'0/1背包问题' 的常用步骤
这五个步骤是解决动态规划问题的模式。
- 确定
dp[j]的含义- 我们可以使用一维
dp滚动数组。滚动数组意味着每次迭代时都会覆盖数组的值。 - 首先，尝试使用问题的
return值作为dp[j]的值来确定dp[j]的含义。如果不行，请尝试另一种方法。 - 所以，
dp[j]表示通过使用前个i个数字，您可以构建的不同表达式的数量，其计算结果为j。 dp[j]是一个整数。
- 我们可以使用一维
确定
dp数组的初始值- 使用一个例子。我们没有使用
示例1：输入：nums = [1,1,1,1,1], target = 3，因为它太特殊，不是推导公式的好例子。 - 我编了一个例子：
nums = [1,2,1,2], target = 4。例子一定要简单，否则完成网格会花太长时间。 - 首先，确定背包的
size。target值可能很小，比如0，所以光靠它不能确定背包的size。- 还应该考虑
nums的总和，以完全覆盖所有背包尺寸。 target可以是负数，但考虑到+和-是任意添加到num的，dp[j]应该围绕0对称。所以负数target的结果dp[target]等于dp[abs(target)]。- 所以背包的
size可以是max(sum(nums), target) + 1。
然后，确定什么是
物品。物品在本题中 就是nums。所以初始化后，`dp` 数组将是： # 0 1 2 3 4 5 6 # 1 0 0 0 0 0 0 # dp # 1 # 2 # 1 # 2可以看到
dp数组大小比背包大小大一。这样，背包大小和索引值就相等了，有助于理解。dp[0]设置为1，表示不使用任何nums就可以实现空背包。另外，它作为起始值，后面的dp[j]都会依赖它，如果为0，则dp[j]的所有值都为0。dp[j] = 0 (j != 0)，说明没有nums是不可能得到j的。
- 使用一个例子。我们没有使用
确定
dp数组的递归公式尝试完成网格，在这个过程中，你会得到推导公式的灵感。
1. 使用第一个数字'1'。 # 0 1 2 3 4 5 6 # 1 0 0 0 0 0 0 # 1 0 1 0 0 0 0 0 # dp # 2 # 1 # 22. 使用第二个数字'2'。 # 0 1 2 3 4 5 6 # 1 0 0 0 0 0 0 # 1 0 1 0 0 0 0 0 # 2 0 1 0 1 0 0 0 # 1 # 23. 使用第三个数字 '1'。 # 0 1 2 3 4 5 6 # 1 0 0 0 0 0 0 # 1 0 1 0 0 0 0 0 # 2 0 1 0 1 0 0 0 # 1 2 0 2 0 1 0 0 # 24. 使用第四个数字 '2'。 # 0 1 2 3 4 5 6 # 1 0 0 0 0 0 0 # 1 0 1 0 0 0 0 0 # 2 0 1 0 1 0 0 0 # 1 2 0 2 0 1 0 0 # 2 4 0 3 0 2 0 1 # dp分析示例
dp网格后，我们可以得出递归公式：dp[j] = dp[abs(j - nums[i])] + dp[j + nums[i]]如果
j < nums[i]，dp[j - nums[i]]将引发数组索引超出范围异常。因此我们使用等于它的dp[abs(j - num)]，因为dp[j]是围绕0对称的，比如dp[-j]等于dp[j]（-j是虚数索引）。
确定
dp数组的遍历顺序dp[j]依赖于dp[abs(j - nums[i])]和dp[j + nums[i]]，因此我们可以按任意顺序遍历dp数组，但必须引用dp的克隆，以防止在迭代过程中修改引用的值。- 对于
j + nums[i] >= dp.length，dp[j + nums[i]]必须为0，因为它们的值太大，超过了nums的最大和。
检查
dp数组的值- 打印
dp以查看其是否符合预期。
- 打印
复杂度
时间复杂度
O(n * sum)
空间复杂度
O(n * sum)
C# #
public class Solution
{
public int FindTargetSumWays(int[] nums, int target)
{
target = Math.Abs(target);
var dp = new int[Math.Max(nums.Sum(), target) + 1];
dp[0] = 1;
foreach (var num in nums)
{
var dc = (int[])dp.Clone();
for (var j = 0; j < dp.Length; j++)
{
dp[j] = dc[Math.Abs(j - num)] + (j + num < dp.Length ? dc[j + num] : 0);
}
}
return dp[target];
}
}
Python #
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
target = abs(target)
dp = [0] * (max(sum(nums), target) + 1)
dp[0] = 1
for num in nums:
dc = dp.copy()
for j in range(len(dp)):
dp[j] = dc[abs(j - num)] + (dc[j + num] if j + num < len(dp) else 0)
return dp[target]
C++ #
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
auto sum = reduce(nums.begin(), nums.end());
target = abs(target);
auto dp = vector<int>(max(sum, target) + 1);
dp[0] = 1;
for (auto num : nums) {
auto dc = dp;
for (auto j = 0; j < dp.size(); j++) {
dp[j] = dc[abs(j - num)] + (j + num < dp.size() ? dc[j + num] : 0);
}
}
return dp[target];
}
};
Java #
class Solution {
public int findTargetSumWays(int[] nums, int target) {
var sum = IntStream.of(nums).sum();
target = Math.abs(target);
var dp = new int[Math.max(sum, target) + 1];
dp[0] = 1;
for (var num : nums) {
var dc = dp.clone();
for (var j = 0; j < dp.length; j++) {
dp[j] = dc[Math.abs(j - num)] + (j + num < dp.length ? dc[j + num] : 0);
}
}
return dp[target];
}
}
JavaScript #
var findTargetSumWays = function (nums, target) {
target = Math.abs(target)
const dp = Array(Math.max(_.sum(nums), target) + 1).fill(0)
dp[0] = 1
for (const num of nums) {
const dc = [...dp]
for (let j = 0; j < dp.length; j++) {
dp[j] = dc[Math.abs(j - num)] + (j + num < dp.length ? dc[j + num] : 0)
}
}
return dp[target]
};
Go #
func findTargetSumWays(nums []int, target int) int {
sum := 0
for _, num := range nums {
sum += num
}
target = int(math.Abs(float64(target)))
dp := make([]int, max(sum, target) + 1)
dp[0] = 1
for _, num := range nums {
dc := slices.Clone(dp)
for j := 0; j < len(dp); j++ {
addition := 0
if j + num < len(dp) {
addition = dc[j + num]
}
dp[j] = dc[int(math.Abs(float64((j - num))))] + addition
}
}
return dp[target]
}
Ruby #
def find_target_sum_ways(nums, target)
target = target.abs
dp = Array.new([ nums.sum, target ].max + 1, 0)
dp[0] = 1
nums.each do |num|
dc = dp.clone
dp.each_with_index do |_, j|
dp[j] = dc[(j - num).abs] + (j + num < dp.size ? dc[j + num] : 0)
end
end
dp[target]
end