一题四解 : 「DFS」&「记忆化搜索」&「全量 DP」&「优化 DP」

题目描述

这是 LeetCode 上的 494. 目标和 ，难度为 中等。

Tag : 「DFS」、「记忆化搜索」、「背包 DP」、「01 背包」

给你一个整数数组 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]) <= 100
• -1000 <= target <= 100

DFS

数据范围只有 2020，而且每个数据只有 +/-+/− 两种选择，因此可以直接使用 DFS 进行「爆搜」。

而 DFS 有「使用全局变量维护」和「接收返回值处理」两种形式。

代码：

class Solution {
    public int findTargetSumWays(int[] nums, int t) {
        return dfs(nums, t, 0, 0);
    }
    int dfs(int[] nums, int t, int u, int cur) {
        if (u == nums.length) {
            return cur == t ? 1 : 0;
        }
        int left = dfs(nums, t, u + 1, cur + nums[u]);
        int right = dfs(nums, t, u + 1, cur - nums[u]);
        return left + right;
    }
}
复制代码

class Solution {
    int ans = 0;
    public int findTargetSumWays(int[] nums, int t) {
        dfs(nums, t, 0, 0);
        return ans;
    }
    void dfs(int[] nums, int t, int u, int cur) {
        if (u == nums.length) {
            ans += cur == t ? 1 : 0;
            return;
        }
        dfs(nums, t, u + 1, cur + nums[u]);
        dfs(nums, t, u + 1, cur - nums[u]);
    }
}
复制代码

• 时间复杂度：O(2^n)O(2n)
• 空间复杂度：忽略递归带来的额外空间消耗。复杂度为 O(1)O(1)

记忆化搜索                                  

不难发现，在 DFS 的函数签名中只有「数值下标 u」和「当前结算结果 cur」为可变参数，考虑将其作为记忆化容器的两个维度，返回值作为记忆化容器的记录值。

由于 cur 存在负权值，为了方便，我们这里不设计成静态数组，而是使用「哈希表」进行记录。

以上分析都在 （题解）403. 青蛙过河 完整讲过。

代码：

class Solution {
    public int findTargetSumWays(int[] nums, int t) {
        return dfs(nums, t, 0, 0);
    }
    Map<String, Integer> cache = new HashMap<>();
    int dfs(int[] nums, int t, int u, int cur) {
        String key = u + "_" + cur;
        if (cache.containsKey(key)) return cache.get(key);
        if (u == nums.length) {
            cache.put(key, cur == t ? 1 : 0);
            return cache.get(key);
        }
        int left = dfs(nums, t, u + 1, cur + nums[u]);
        int right = dfs(nums, t, u + 1, cur - nums[u]);
        cache.put(key, left + right);
        return cache.get(key);
    }
}
复制代码

• 时间复杂度：O(n * \sum_{i = 0}^{n - 1} abs(nums[i]))O(n∗∑i=0n−1abs(nums[i]))
• 空间复杂度：忽略递归带来的额外空间消耗。复杂度为 O(n * \sum_{i = 0}^{n - 1} abs(nums[i]))O(n∗∑i=0n−1abs(nums[i]))

动态规划

能够以「递归」的形式实现动态规划（记忆化搜索），自然也能使用「递推」的方式进行实现。

根据记忆化搜索的分析，我们可以定义：

f[i][j]f[i][j] 代表考虑前 ii 个数，当前计算结果为 jj 的方案数，令 nums 下标从 11 开始。

那么 f[n][target]f[n][target] 为最终答案，f[0][0] = 1f[0][0]=1 为初始条件：代表不考虑任何数，凑出计算结果为 00 的方案数为 11 种。

根据每个数值只能搭配 +/-+/− 使用，可得状态转移方程：

f[i][j] = f[i - 1][j - nums[i - 1]] + f[i - 1][j + nums[i - 1]]f[i][j]=f[i−1]

[j−nums[i−1]]+f[i−1][j+nums[i−1]]

到这里，既有了「状态定义」和「转移方程」，又有了可以滚动下去的「有效值」（起始条件）。

距离我们完成所有分析还差最后一步。

当使用递推形式时，我们通常会使用「静态数组」来存储动规值，因此还需要考虑维度范围的：

• 第一维为物品数量：范围为 nums 数组长度
• 第二维为中间结果：令 s 为所有 nums 元素的总和（题目给定了 nums[i] 为非负数的条件，否则需要对 nums[i] 取绝对值再累加），那么中间结果的范围为 [-s, s][−s,s]

因此，我们可以确定动规数组的大小。同时在转移时，对第二维度的使用做一个 s 的右偏移，以确保「负权值」也能够被合理计算/存储。

代码：

class Solution {
    public int findTargetSumWays(int[] nums, int t) {
        int n = nums.length;
        int s = 0;
        for (int i : nums) s += Math.abs(i);
        if (t > s) return 0;
        int[][] f = new int[n + 1][2 * s + 1];
        f[0][0 + s] = 1;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for (int j = -s; j <= s; j++) {
                if ((j - x) + s >= 0) f[i][j + s] += f[i - 1][(j - x) + s];
                if ((j + x) + s <= 2 * s) f[i][j + s] += f[i - 1][(j + x) + s];
            }
        }
        return f[n][t + s];
    }
}
复制代码

• 时间复杂度：O(n * \sum_{i = 0}^{n - 1} abs(nums[i]))O(n∗∑i=0n−1abs(nums[i]))
• 空间复杂度：O(n * \sum_{i = 0}^{n - 1} abs(nums[i]))O(n∗∑i=0n−1abs(nums[i]))

动态规划（优化）

在上述「动态规划」分析中，我们总是尝试将所有的状态值都计算出来，当中包含很多对「目标状态」不可达的“额外”状态值

即达成某些状态后，不可能再回到我们的「目标状态」。

例如当我们的 targettarget 不为 -s−s 和 ss 时，-s−s 和 ss 就是两个对「目标状态」不可达的“额外”状态值，到达 -s−s 或 ss 已经使用所有数值，对 targettarget 不可达。

那么我们如何规避掉这些“额外”状态值呢？

我们可以从哪些数值使用哪种符号来分析，即划分为「负值部分」&「非负值部分」，令「负值部分」的绝对值总和为 mm，即可得：

(s - m) - m = s - 2 * m = target(s−m)−m=s−2∗m=target

变形得：

m = \frac{s - target}{2}m=2s−target

问题转换为：只使用 ++ 运算符，从 nums 凑出 mm 的方案数。

这样「原问题的具体方案」和「转换问题的具体方案」具有一一对应关系：「转换问题」中凑出来的数值部分在实际计算中应用 -−，剩余部分应用 ++，从而实现凑出来原问题的 targettarget 值。

另外，由于 nums 均为非负整数，因此我们需要确保 s - targets−target 能够被 22 整除。

同时，由于问题转换为 从 nums 中凑出 mm 的方案数，因此「状态定义」和「状态转移」都需要进行调整（01 背包求方案数）：

定义 f[i][j]f[i][j] 为从 nums 凑出总和「恰好」为 jj 的方案数。

最终答案为 f[n][m]f[n][m]，f[0][0] = 1f[0][0]=1 为起始条件：代表不考虑任何数，凑出计算结果为 00 的方案数为 11 种。

每个数值有「选」和「不选」两种决策，转移方程为：

f[i][j] = f[i - 1][j] + f[i - 1][j - nums[i - 1]]f[i][j]=f[i−1][j]+f[i−1][j−nums[i−1]]

代码：

class Solution {
    public int findTargetSumWays(int[] nums, int t) {
        int n = nums.length;
        int s = 0;
        for (int i : nums) s += Math.abs(i);
        if (t > s || (s - t) % 2 != 0) return 0;
        int m = (s - t) / 2;
        int[][] f = new int[n + 1][m + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for (int j = 0; j <= m; j++) {
                f[i][j] += f[i - 1][j];
                if (j >= x) f[i][j] += f[i - 1][j - x];
            }
        }
        return f[n][m];
    }
}
复制代码

• 时间复杂度：O(n * (\sum_{i = 0}^{n - 1} abs(nums[i]) - target))O(n∗(∑i=0n−1abs(nums[i])−target))
• 空间复杂度：O(n * (\sum_{i = 0}^{n - 1} abs(nums[i]) - target))O(n∗(∑i=0n−1abs(nums[i])−target))

最后

这是我们「刷穿 LeetCode」系列文章的第 No.494 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。