LC总结-DP相关解题思路

1. 入门

对于初学者来说，最难的是如何找到递推关系，我们需要通过一套方法来总结、训练。

动态规划（DP）思路：

第一步：先思考回溯怎么写（入参与返回值、递归到哪里、递归边界和入口）

第二步：改成记忆化搜索（就是用数组或者哈希表存储已经求解过的结果）

第三步：翻译成递推

计算时间复杂度公式：状态个数 * 单个状态的计算时间

2. 以 LC198 打家劫舍为例

https://leetcode.cn/problems/house-robber/description/

2.1 回溯 + 记忆化

当前操作：枚举第 i 个房子选 / 不选

子问题：从前 i 个房子中得到的最大金额和

下一个问题：选（前 i - 2 个房子中得到的最大金额和）、不选（前 i - 1 个房子中得到的最大金额和）

得到：dfs(i) = max(dfs(i - 1), dfs(i - 2) + nums[i])

class Solution {
    private HashMap<Integer, Integer> map = new HashMap<>();

    public int dfs(int[] nums, int i) {
        if (i < 0) {
            return 0;
        }
      	// 记忆化搜索
        if (map.containsKey(i)) {
            return map.get(i);
        }
        int res = Math.max(dfs(nums, i - 1), dfs(nums, i - 2) + nums[i]);
        map.put(i, res);
        return res;
    }

    public int rob(int[] nums) {
        return dfs(nums, nums.length - 1);
    }
}

2.2 改成递推

由上面已知 dfs(i) = max(dfs(i - 1), dfs(i - 2) + nums[i])

改成递推的步骤：

dfs -> f 数组
边界条件 -> f 数组的初始化
递归 -> 循环

考虑到数组越界问题，我们可以对 f 数组中 i 同时加2，变为：

f(i + 2) = max(f[i + 1], f[i] + nums[i])

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 2];
        for(int i = 0; i < n; i++){
            f[i+2] = Math.max(f[i+1], f[i] + nums[i]);
        }
        return f[n+1];
    }
}

由于只用到了上个结果 f[i+1] 和上上个结果 f[i]，我们可以考虑对空间进行优化：

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int f0 = 0, f1 = 0, newF = 0;
        for (int i = 0; i < n; i++) {
            newF = Math.max(f1, f0 + nums[i]);
            f0 = f1;
            f1 = newF;
        }
        return newF;
    }
}

3. 以 0-1 背包问题为例

https://leetcode.cn/problems/target-sum/description/

3.1 回溯

当前操作：枚举第 i 个物品选 / 不选；不选，剩余容量不变；选，剩余容量减少 w[i]

子问题：剩余容量为 c 时，从前 i 个物品中得到的最大价值和

下一个问题：不选（剩余容量为c，前 i - 1 个物品中得到的最大价值和）、选（剩余容量为 c - w[i]，前 i - 1 个物品中得到的最大价值和）

得到：dfs(i, c) = max(dfs(i - 1, c), dfs(i - 1, c - w[i]) + v[i])

3.2 套在 LC494 目标和上

https://leetcode.cn/problems/target-sum/description/

这道题就是 0-1 背包问题的变种，通过推导，我们要在数组中找一些数，满足以下条件：

// 正号的数的和为 p
// 负号的数的和为 s - p
// p - (s - p) = target
// p = (s + target) / 2

s + target 需要满足：是偶数、不小于0（因为数组元素都是正数）

class Solution {
    public int dfs(int[] nums, int i, int c) {
        if (i < 0) {
            if (c == 0) {
                return 1;
            } else {
                return 0;
            }
        }
        if (c < nums[i]) {
            return dfs(nums, i - 1, c);
        }
        return dfs(nums, i - 1, c) + dfs(nums, i - 1, c - nums[i]);
    }

    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        target += sum;
        if (target < 0 || target % 2 != 0) {
            return 0;
        }
        target /= 2;

        return dfs(nums, nums.length - 1, target);
    }
}

3.3 改为递推

由 dfs(i, c) = max(dfs(i - 1, c), dfs(i - 1, c - w[i]) + v[i])

可得 f[i][c] = max(f[i-1][c], f[i-1][c-w[i]] + v[i])

为了避免数组越界，对 f 中的 i 加 1

f[i+1][c] = max(f[i][c], f[i][c-w[i]] + v[i]) 或者 f[i][c]（容量不足的情况）

把 max 改为加法

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        target += sum;
        if (target < 0 || target % 2 != 0) {
            return 0;
        }
        target /= 2;
        
        int n = nums.length;
        int[][] f = new int[n + 1][target + 1];
        f[0][0] = 1; // 对应i=0，c=0

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= target; j++) {
                if (j < nums[i]) {
                    f[i + 1][j] = f[i][j];
                } else {
                    f[i + 1][j] = f[i][j] + f[i][j - nums[i]];
                }
            }
        }
        return f[n][target];
    }
}

最后考虑空间优化，每次只有数组中的两个位置参与状态转移，可以将 i 改成 i % 2，最后 n 改为 n % 2

4. 以腾讯音乐笔试题为例

前面几道题都是视频里的样例题，下面试着把上面这套方法用起来，结合到4月18日晚的腾讯音乐笔试第三题中。

题目（大概是这样）：

给定一个字符串 s 和一个数组 nums，它们长度相等，字符串第 i 个字符代表数组第 i 个数的颜色，‘R’ 代表红色（已染色），‘W’ 代表未染色。现在要求有多少种染色方案，使得红色节点的和为偶数。

测试样例：

s = “RWWW”，nums=[1, 2, 3, 4]

一共有 4 种方案，分别是：{1, 3, 4}，{1, 3}，{1, 2, 3}，{1, 2, 3, 4}

下面是解题流程。

4.1 递归

考虑递归的三个问题。

当前操作：对当前节点染色（红色节点和 + nums[i]），对当前节点不染色（红色节点和不变）
子问题：当前红色节点和为 s，求前 i 个红色节点和为偶数的方案
下一个子问题：不染色（红色节点和为 s，前 i 个红色节点和为偶数的方案）、染色（红色节点和为 s + nums[i]，前 i 个红色节点和为偶数的方案）

得到：dfs(i, s) = dfs(i - 1, s) + dfs(i - 1, s + nums[i])

public class Test {
    public static int dfs(int[] nums, String colors, int i, int tmpSum) {
        // 边界条件
        if (i < 0) {
            if (tmpSum % 2 == 0) {
                return 1;
            } else {
                return 0;
            }
        }
        if (colors.charAt(i) == 'W') {
            // 只有未染色的节点才能选择染或者不染
            return dfs(nums, colors, i - 1, tmpSum) + dfs(nums, colors, i - 1, tmpSum + nums[i]);
        }
        return dfs(nums, colors, i - 1, tmpSum);
    }

    public static void main(String[] args) {
        String colors = "RWWW";
        int[] nums = new int[]{1, 2, 3, 4};
        int redSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (colors.charAt(i) == 'R') {
                redSum += nums[i];
            }
        }
        System.out.println(dfs(nums, colors, nums.length - 1, redSum));
    }
}

接着用一个二维数组存储搜索过的值，即可改为记忆化搜索。

4.2 改为递推

也是三步走：

dfs -> f 数组：

f[i, s] = f[i - 1][s] + f[i - 1][s + nums[i]]

为了防止下标越界，对 f 中的 i 都加1，得到递推式：

f[i + 1, s] = f[i][s] + f[i][s + nums[i]]
边界条件 -> f 数组的初始值：f[0][tmpSum] = 1（遍历 0 到 tmpSum，偶数为1）
递归 -> 循环

public class Test {
    public static void main(String[] args) {
        String colors = "RWWW";
        int[] nums = new int[]{1, 2, 3, 4};
        int redSum = 0, sum = 0;

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (colors.charAt(i) == 'R') {
                redSum += nums[i];
            }
        }

        // 递推做法
        int[][] f = new int[nums.length + 1][sum + 1];

        // 初始化数组 对应 tmpSum % 2 == 0 时返回1
        for (int i = 0; i <= sum; i++) {
            if (i % 2 == 0) {
                f[0][i] = 1;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            for (int s = 0; s <= sum; s++) {
                if (colors.charAt(i) == 'W' && s + nums[i] <= sum) {
                    f[i + 1][s] = f[i][s] + f[i][s + nums[i]];
                } else {
                    f[i + 1][s] = f[i][s];
                }
            }
        }
        // 入参和 dfs 对应
        System.out.println(f[nums.length][redSum]);
    }
}