目标和 -「回溯」&「动规」

494. 目标和

本篇文章将介绍 目标和，但又不仅仅只介绍该题目，而是从「回溯」和「动规」的角度分析该题目，同时也对「回溯」和「动规」进行了一波对比！血赚！！

暴力回溯

本小节主要分析如何通过回溯暴力求解，至于如何优化放在下一小节。关于回溯详细讲解可见 回溯 (DFS) 算法框架

如果单纯直接暴力解决该问题，其实不算难，因为这个问题就是一个很基础的回溯模版题

我们每一次的选择无非就是「+ / -」，而结束条件就是「递归完数组后，满足目标和 或 不满足目标和」

很容易可以写出代码：

// 记录当前和 (可以理解为「回溯」框架里的路径)
private int sum = 0;
// 记录所有满足条件的解的个数
private int res = 0;
public int findTargetSumWays(int[] nums, int target) {
    backtrack(nums, 0, target);
    return res;
}
private void backtrack(int[] nums, int index, int target) {
    // 递归完数组，不满足目标和，直接返回
    if (index == nums.length && sum != target) return ;
    // 递归完数组，满足目标和，可行解 +1
    if (index == nums.length && sum == target) {
        res++;
        return ;
    }
    // 处理当前元素 nums[index]
    // 选择 +
    sum += nums[index];
    // 递归处理下一个元素
    backtrack(nums, index + 1, target);
    // 撤销选择
    sum -= nums[index];
    
    // 选择 -
    sum -= nums[index];
    backtrack(nums, index + 1, target);
    // 撤销选择
    sum += nums[index];
}

是不是很 easy，完全就是套模版。但是时间直接爆炸 (虽然过了，但是很不满意！！)

回溯 + 备忘录

其实「回溯」的优化方法只有一种，就是判断是否存在「重叠子结构」。如果存在，就用「备忘录」记录子结构的结果，避免重复计算

显然这个问题是存在「重叠子结构」滴！但是怎么找出来呢？？我们把上面的结构稍微优化一下，方便看出「重叠子结构」

​x
// 选择 +
backtrack(nums, index + 1, target - nums[index]);

// 选择 -
backtrack(nums, index + 1, target + nums[index]);

现在我们极端假设nums[index] = 0，是不是这两个递归就变成一模一样的了，这就是「重叠子结构」

那我们如何存储「重叠子结构」的结果呢？？我们就需要思考如何才能描述一个「子结构」

假设[1,2,3,...,i,...,n-1], target = 10

如果现在我们已经计算出一种组合使得[1,2,3,...,i] = 5，那么我们现在只需要计算[i+1,...,n-1] = 10 - 5存在多少种组合就可以

如果后面我们又计算出另外一种组合使得[1,2,3,...,i] = 5，我们现在依旧需要知道[i+1,...,n-1] = 10 - 5的组合数

所以我们如果把[i+1,...,n-1] = 10 - 5的组合数记录下来，下次遇到就可以直接用了，我们可以用一个Map<Integer, Integer>[]来记录

经过上面的分析，就可以很容易写出优化后的代码：

xxxxxxxxxx
// emeoMap[i] : 表示 [i...n-1] 所有的结果的组合数
// 例：emeoMap[i].get(5) 表示 [i...n-1] 可以组合成 5 的所有组合数
private Map<Integer, Integer>[] emeoMap;
public int findTargetSumWays(int[] nums, int target) {
    emeoMap = new HashMap[nums.length];
    for (int i = 0; i < nums.length; i++) emeoMap[i] = new HashMap<>();
    return backtrack(nums, 0, target);
}
private int backtrack(int[] nums, int index, int target) {

    if (index == nums.length && target != 0) return 0;

    if (index == nums.length && target == 0) return 1;
    
    // 如果存在，直接用
    if (emeoMap[index].containsKey(target)) return emeoMap[index].get(target);

    int count = backtrack(nums, index + 1, target - nums[index]) + backtrack(nums, index + 1, target + nums[index]);
    
    // 存储子问题结果
    emeoMap[index].put(target, count);

    return count; 
}

经过一波优化后，现在的执行时间如下：(是不是又感觉自己可以了，但是我还是不满意！！！)

动态规划

先来分析一下这个问题。从另一个角度看问题，你会发现新世界的大门！！

说白了，这个题目就是把nums[]划分为两个部分A && B，对A集合内的元素执行+操作，对B集合内的元素执行-操作。所以有sum(A) - sum(B) = target

基于上面的前提，我们来一波转换：

xxxxxxxxxx
sum(A) + sum(B) = sum(nums)
sum(A) - sum(B) = target
sum(A) = target + sum(B)
2 * sum(A) = target + sum(B) + sum(A)
sum(A) = (target + sum(nums)) / 2

所以现在我们的问题转换成「能否在集合nums中找到恰好和为sum(A)的组合」。这不就变成了题目 分割等和子集 嘛！！关于这个题目的详细分析可见 经典动态规划：子集背包问题

关于dp[][]数组的定义有一点不一样，本问题的定义如下：对于前i个元素，当前背包容量j，这种情况下背包可以恰好装满的所有组合数

与此同时，base case 也有一点不一样！！dp[0][...] = 0显然都是没有满足要求的组合滴，但是dp[0][0] = 1是个例外。需要注意的是，dp[...][0]并不能算进 base case 中

至此，我们可以写出代码：

xxxxxxxxxx
public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int n : nums) sum += n;
    // 排除非法的情况
    if (sum < Math.abs(target) || (target + sum) % 2 == 1) return 0;
    return subsets(nums, (target + sum) / 2);
}
private int subsets(int[] nums, int target) {
    // dp[i][j] 的含义：前 i 个元素，可以恰好组成和为 j 的数量
    int[][] dp = new int[nums.length + 1][target + 1];
    //base case : dp[0][0] = 1;
    dp[0][0] = 1;
    for (int i = 1; i < dp.length; i++) {
        for (int j = 0; j < dp[0].length; j++) {
            // 超出，不能选择
            if (j - nums[i - 1] < 0) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
        }
    }
    return dp[nums.length][target];
}

下面看看动规的执行时间吧！！(是不是再次感觉自己又可以了，这次貌似真的可以了hhhhh)

动态规划优化

dp 二维 -> 一维

先留个坑，以后再补！！！！

今天 (2022-09-10 22:09:45) 来补上这个坑！！

关于「二维 -> 一维」的优化可以先看 动态规划之最长回文子序列「dp 空间优化」

注：第二重循环需要反向遍历

如果正向遍历，新算出来的dp[j]会覆盖掉上一行的值，随着不断的向右，会用到左边的值，所以造成了上一行值的丢失

而如果反向遍历，随着不断的向左，一定不会用到右边的值，所以可以覆盖！！

具体如下图所示：

此时dp[j - nums[i - 1]]的值已经被覆盖了，所以正向遍历会出现问题！！

xxxxxxxxxx
public int findTargetSumWays(int[] nums, int target) {
    int sum = 0, n = nums.length;
    for (int i = 0; i < n; i++) sum += nums[i];
    if (sum < Math.abs(target) || (sum + target) % 2 != 0) return 0;
    target = (sum + target) / 2;
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        // 注意：需要反向遍历
        for (int j = target; j >= 0; j--) {
            if (j - nums[i - 1] < 0) dp[j] = dp[j];
            else dp[j] = dp[j] + dp[j - nums[i - 1]];
        }
    }
    return dp[target];
}