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

这是我参与更文挑战的第 7 天，活动详情查看：更文挑战

题目描述

这是 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

数据范围只有 $20$ ，而且每个数据只有 $+/-$ 两种选择，因此可以直接使用 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(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 * \sum_{i = 0}^{n – 1} abs(nums[i]))$

动态规划

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

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

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

那么 $f[n][target]$ 为最终答案， $f[0][0] = 1$ 为初始条件：代表不考虑任何数，凑出计算结果为 $0$ 的方案数为 $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 的右偏移，以确保「负权值」也能够被合理计算/存储。

代码：

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 * \sum_{i = 0}^{n – 1} abs(nums[i]))$

动态规划（优化）

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

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

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

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

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

$(s – m) – m = s – 2 * m = target$

变形得：

$m = \frac{s – target}{2}$

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

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

另外，由于 nums 均为非负整数，因此我们需要确保 $s – target$ 能够被 $2$ 整除。

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

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

最终答案为 $f[n][m]$ ， $f[0][0] = 1$ 为起始条件：代表不考虑任何数，凑出计算结果为 $0$ 的方案数为 $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];
    }
}
复制代码