刷题笔记8-动态规划

一、核心原理

刷过一些题后，感觉动态规划最核心的就是 dp 数组 + 状态转移方程

【dp数组】是为了避免重复计算而带来的高复杂度

【状态转移方程】是为了将问题进行分解成更加简单的子结构

所以动态规划的核心思想就是：

1、自底向上（迭代）：从最简子结构开始，不断向上计算，在计算过程中将对应子结构的值存在 dp数组 中，使得更复杂结构的问题在分解后可以直接找到答案。

2、自顶向下（递归） ：从当前问题规模出发，通过递归不断分解问题直至 base case，计算出base case后，再从最深的递归函数开始不断返回，向上计算，最后求解出问题的答案。

要写出动态规划的解法，最重要的就是写出 状态转移方程。有了状态转移方程，就知道需要保存什么值，就可以推出dp数组的定义。

首先要明确 状态。这个状态是会影响问题规模的量。在背包问题中，很明显问题的规模主要和 物品的数量 以及 背包的容量 相关。因为如果这两个量的值很小，那么问题就会很简单，反之就会很复杂。

明确状态之后，就要寻找如何转移。转移的目的是降低问题的规模（通过改变状态）。那么在背包问题中，我们要求解的是 在当前给定数量(\(N\))的物品 和 给定容量(\(W\))的背包的前提下的某个问题，我们用 \(f(N, W)\)来表示。

而我们想要找出来的是 \(f(N,W)\) 能够用某些更小规模的问题来表示（可以理解为数列中的递推公式），例如 \(f(N,W) = f(N-1,W) + f(N, W-1)\)

最后要去找到base case的值，例如\(f(0,W)\)或者\(f(N,0)\)，因为所以的状态转移都是建立在base case的基础上的。

二、经典动态规划问题

这里主要讲两类问题，分类的主要是状态转移方程的类型。

1、单参数

【300.最长递增子序列】

【53.最大子序和】

它们的状态转移方程都只有一个参数（dp数组都是一维的）

【300.最长递增子序列】中的状态转移方程：$f(i) = max(f(i), f(j)+1) $ \(j = [i+1, ... n-1]\)，其中\(f(i)\)表示以第\(i\)个元素结尾的最长严格递增子序列的长度。

那么核心部分的代码也就很好写了

vector<int> mem(n, 1);
int res = 1;
for (int i = 1; i < n; i++){
    for (int j = 0; j < i; j ++) {
        if (nums[j] >= nums[i]) continue;
        mem[i] = max(mem[i], mem[j]+1);
        if (res < mem[i]) res = mem[i];
    }
}

2、双参数

【1143.最长公共子序列】

【72.编辑距离】

【10.正则表达式匹配】

这一类的问题涉及到两个状态，但本质上还是第一类问题，只是由于字符串/数组变成了两个，所以需要两个参数来记录状态。

以【10.正则表达式状态匹配】为例。存在 一个待匹配的字符串 str 和 一个模板串 pattern，那么状态就有两个： str 的长度和 pattern 的长度，那这个问题的解就可以表示为 \(f(N, M)\)

然后就要考虑如何转移状态化简问题的解。我们先任取两个值 i，j，分别表示【只考虑str的前i个字符】以及【只考虑pattern的前j个字符】，这样我们要求解的就是f(str.length(), pattern.length())了。

由于\(f(i,j)\)之前的子问题肯定都已经计算好了，所以我们就只要考虑如何减小i、j这两个参数。下面就涉及到问题的细节，在这个问题中，到状态转移到i和j时，考虑pattern的第j个字符是什么？我们分为两种情况：'*'和不是'*'，原因在于'*'是可以匹配多个的，是变化的。

• 如果是'*'：就要看前一个字符是否和str的第i个字符【相同】
  • 不相同：dp[i][j]转移到dp[i][j-2]
  • 相同：就要选择是否要去匹配str的第i个字符
    • 不去匹配：dp[i][j]转移到dp[i][j-2]
    • 要匹配：dp[i][j]转移到dp[i-1][j]
• 如果不是'*'：就看str的第i个字符和pattern的第j个字符是否相同
  • 相同：dp[i][j]转移到dp[i-1][j-1]
  • 不相同：dp[i][j] = false

【完整代码】如下：

public boolean isMatch(String s, String p) {
    int n = s.length();
    int m = p.length();

    boolean[][] dp = new boolean[n+1][m+1];
    dp[0][0] = true;
    for(int i = 0; i <= n; i++){ // 从0开始是为了看是否能够匹配空串；填上dp数组的最上面一行；就是确定base case
        for(int j = 1; j <= m; j++){
            if(p.charAt(j - 1) == '*'){
                // 匹配0个
                dp[i][j] = dp[i][j-2];
                // 匹配1个
                if(i == 0) continue;
                if(s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.'){
                    dp[i][j] = dp[i][j] || dp[i-1][j];
                }
            } else {
                if(i == 0) continue;
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.'){
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
    }
    return dp[n][m];
}

三、背包问题

1、类型

1.1、0-1背包问题

【问题描述】

给定一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性，其中第i个物品的重量为wt[i]，价值为val[i]，请问用这个背包最多可以装多少价值的物品？

1.2、完全背包问题

【518.零钱兑换Ⅱ】

给定不同面额的硬币和一个总金额，计算出可以凑成总金额的硬币组合数，假设每一种面额的硬币有无限个。

转换为背包问题，就是

有一个最大容量为 amount 的背包，有一系列物品 coins，物品的重量为 coins[i]，每个物品的数量无限，请问有多少种方法，能够恰好把背包装满？

由于每个物品的数量是无限的，所以被称为【完全背包问题】

1.3、子集背包问题

【416.分割等和子集】

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得这两个子集的元素和相等。

其实类似于0-1背包问题

有一堆物品 nums，物品重量为 nums[i]，物品重量之和为 sum。有一个容量为 sum / 2 的背包，是否存在一种方法能够恰好装满这个背包？

2、分析

由于都可以转换为情景相似的背包问题，所以就可以放在一起分析。

这里我们挑完全背包问题作为例子，【518.零钱兑换Ⅱ】

1. 明确状态：\(N\)：前\(N\)个硬币；\(W\)：总金额
2. 明确转移：需要求解的是 \(f(N, W)\)，即给定前\(N\)个硬币恰好可以组成\(W\)金额的组合数。这么定义了之后，我们就可以很轻易的写出最简单问题的答案：\(f(0, W) = 0\)和\(f(N, 0) = 1\)
3. 如何转移：对于 \(f(N,W)\)，我们考虑第\(N\)个硬币P。如果我们在组合过程中不使用P，那么问题就被转化为了 \(f(N-1,W)\)。如果我们在组合过程中要使用P，那么问题就被转化为了\(f(N, W-wt[P])\)。
4. 所以我们可以得出状态转移方程：\(f(N,W) = f(N-1,W)+f(N,W-wt[P])\)

写出状态转移方程之后，我们就可以知道如何定义 dp数组 了。

int[][] dp = new int[][];
// dp[i][j]: 前i个硬币组合出j金额的种数

我们就可以用dp数组来表示状态转移方程

dp[i][j] = dp[i-1][j] + dp[i][j - <第i个硬币的面值>]

[3]有一个比较难理解的点，就是为什么使用了P，问题被转化成了\(f(N, W-wt[P])\)，而不是\(f(N-1, W-wt[P])\)

​ 可能会感觉是 \(N-1\)，毕竟第\(N\)个硬币已经用过了，但是也可能\(W-wt[P]\)金额组合中也用了第\(N\)个硬币，所以不能确定硬币数，只能确定金额数。

3、代码和改进

代码

【518.零钱兑换Ⅱ】完整代码如下：

public int change(int amount, int[] coins) {
    int n = coins.length;
    int[][] dp = new int[n+1][amount+1];
    for(int i = 0; i <= n; i++) dp[i][0] = 1;
    // 目标就是求 dp[n][amount]
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= amount; j++){
            if(j < coins[i-1]){
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]];
            }
        }
    }
    return dp[n][amount];
}

状态压缩

最后，还要再探讨一下状态压缩问题，即可以使用一维dp数组，使得空间复杂度从\(O(NW)\)降为\(O(W)\)

这里主要选取【518.零钱兑换Ⅱ】和【416.分割等和子集】两个问题

首先写出它们的状态转移方程

// 518.零钱兑换Ⅱ
dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]];
// 416.分割等和子集
dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]];

可以发现，dp[i][j]只和dp[i][...]以及dp[i-1][...]有关系。

改成一维数组后

int[] dp = new int[amount];

在第i轮迭代开始之前，dp数组中的值就等价于之前的 dp[i-1][...]

所以只要控制遍历顺序（正向或逆向），使得在遍历dp[j]时，dp[j-?]的值已经更新（dp[i][j-?]）或者没有更新（dp[i-1][j-?]），即可实现状态的转移。

最后附上使用一维数组解决的代码

注意两段代码的第二层循环，就是通过正向遍历和逆向遍历实现在计算dp[j]时dp[j-?]的已更新和未更新

// 518.零钱兑换Ⅱ
public int change(int amount, int[] coins) {
    int n = coins.length;
    int[] dp = new int[amount+1];
    dp[0] = 1;
    // 目标就是求 dp[amount]
    for(int i = 0; i < n; i++){
        for(int j = 1; j <= amount; j++){
            if(j < coins[i]) continue;
            dp[j] = dp[j] + dp[j - coins[i]];
        }
    }
    return dp[amount];
}

// 416.分割等和子集
public boolean canPartition(int[] nums) {
    // 前置判断
    int sum = 0; int n = nums.length;
    if (n == 1) return false;
    for (int i : nums) sum += i;
    if(sum % 2 == 1) return false;
    int target = sum / 2; // 背包中的目标值

    boolean[] dp = new boolean[target+1];
    dp[0] = true;
    for(int i = 0; i < n; i++){
        for(int j = target; j >= 1; j--){
            if(j < nums[i]) continue;
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    return dp[target];
}