05-数据结构与算法
动态规划

动态规划理论基础

# 1. 基本思想

动态规划算法与分治法类似，其基本思想都是将待求解问题分解成若干个子问题，先求解子问题，再结合这些子问题的解得到原问题的解。（通过子问题的解得到原问题的解，满足最优子结构性质）

与分治法不同的是，适合用动态规划法求解的问题经分解得到的子问题往往不是互相独立的。⭐ 存在「重叠子问题」，如果分治法的话效率会极其低下，所以需要「备忘录」或者「辅助表 DP table」来记录所有已解决的子问题的答案，避免不必要的计算。

总结来说，动态规划算法的总体思想就是保存已解决的子问题的答案，在需要时使用，从而避免大量重复计算

分治法：

最优子结构性质

动态规划：

最优子结构性质

存在重叠子问题

其实动态规划的核心就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」才能正确地穷举。在实际的算法问题中，写出状态转移方程是最困难的。

⭐ 动态规划算法适用于最优化问题，通常有以下 4 个步骤：

① 找出最优解的性质，并刻画其结构特征（最优子结构）
② 递归地定义最优值（状态转移方程）
③ 以自底向上的方式计算最优值（实现状态转移方程）
④ 根据计算最优值时得到的信息，构造最优解（若不需要最优解则第 ④ 步可省略）

# 2. 引例：矩阵连乘问题

【问题描述】：给定 n 个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

例如，给定三个连乘矩阵{A1，A2，A3}的维数分别是，和，采用，乘法次数为 $次$ ，而采用，乘法次数为 $次$ 乘法，显然，最好的次序是，乘法次数为7500次。

首先考虑计算两个矩阵乘积所需的计算量。假设 A 是的矩阵，B 是的矩阵，则 C = AB 是一个的矩阵，一共需要次数乘。在计算多个矩阵的连乘的时候，不同的加括号方式对整个计算量来说具有很大的影响。下面我们用动态规划法来求解该问题：

# ① 最优子结构

该问题符合【最优子结构】：

# ② 状态转移方程

辅助表 m[i][j] 记录了最优值，即计算 A[i:j] 所需的最少数乘次数。同时确定了计算 A[i:j] 的最优次序中的断开位置 k。

若将对应 m[i:j] 的断开位置 k 记为 s[i][j]，则在计算出最优质 m[i][j] 后，可递归地由 s[i][j] 构造出相应的最优解。

# ③ 实现状态转移方程

由上一步的递归式可以看出，递归的过程中会出现很多的重复子问题。可以用两个 n * n 维的辅助表：

m[n][n] 表示最优乘积代价（最少数乘次数）
s[n][n] 表示每个子问题的最优分割位置 k

对于一组矩阵: $A1(3035),A2(3515),A3(155),A4(510),A5(1020),A6(2025) $ ，个数 n = 6

那么 p 数组保存它们的行数和列数：，共有 n+1 即 7 个元素

p[0], p[1] 分别代表第一个矩阵的行数和列数，p[1],p[2] 分别代表第二个矩阵的行数和列数...... p[5],p[6] 代表第六个矩阵的行数和列数

🔗 下图来源动态规划算法之矩阵连乘问题思路 (opens new window)

⭐ 辅助表 s[n][n] 可以由 2 种方法构造（下节会详细讲解）：

一种是**自底向上（动态规划算法）**构建，该方法要求按照递增的方式逐步填写子问题的解，也就是先计算 2 个矩阵连乘的最优分割位置，然后计算 3 个矩阵连乘的最优分割位置，直到长度 n；
另一种是自顶向下（备忘录法），该方法将表的每个元素初始化为某特殊值(本问题中可以将最优乘积代价设置为一极大值)，以表示待计算，在递归的过程中逐个填入遇到的子问题的解。

采用动态规划的方式，则计算顺序为：

：

辅助表 m[i][j]代表从矩阵 $，，$ 直到矩阵连乘的最小的相乘次数，比如 m[2][5] 代表矩阵 A2 A3 A4 A5 最小的相乘次数，即最优的乘积代价。我们看上图，从矩阵 A2 到 A5 有三种断链方式：A2{A3A4A5}、{A2A3}{A4A5}、{A2A3A4}A5，我们分别算出这三个不同断链方式的总乘积次数，然后选出最小的一个，就是 m[2][5] 的值。同时保留断开的位置 k 在 s[2][5] 数组中。

即 m[2][5] = 7125, s[2][5] = 3

// p 存储矩阵的行列数
// n 表示一共多少个矩阵
// m 数组存储每个子问题的最优值(计算量)
// s 数组存储每个子问题的最优断开位置
public void MatixChain(int[] p, int n, int[][] m, int[][] s){

    // m[i][i]只有一个矩阵，所以相乘次数为0，即 m[i][i] = 0;
    for(int i = 1; i <= n; i ++)
        m[i][i] = 0; 

    // r 表示矩阵链的长度（r 个矩阵相乘）
    for(int r = 2; r <= n; r ++){
        for(int i = 1; i <= n-r+1; i ++){
            // 以 i 为起始位置，j 为长度为 n 的矩阵链的末位
            int j = i + r - 1;
            // 将链 A[i:j] 划分为 A(i) * ( A[i+1:j] ) 
            m[i][j] = m[i+1][j] + p[i-1] * p[i] * p[j];
            s[i][j] = i; // 初始化断开点位置

            // 将链 A[i:j] 划分为 A[i:k] * A[k+1:j]
            for(int k = i + 1; k < j; k ++){
                int temp = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
                if(temp < m[i][j]){
                    m[i][j] = temp; // 更新最优值
                    s[i][j] = k; // 更新断开点位置
                }
            }
        }
    }
}

至此，我们比计算出来矩阵连乘的最少数乘次数，接下来我们需要计算什么样的的计算次序能够达到此最少数乘次数 👇

# ④ 构造最优计算次序

// 返回 s 数组 i~j 范围内的最优值
public void Traceback(int i, int j, int[][] s){
    if(i == j)
       return ;
    Traceback(i, s[i][j], s);
    Traceback(s[i][j]+1, j, s);
    System.out.println("Multiply  A" + i + "," + s[i][j] + " and A" + (s[i][j] + 1) + "," + j);
}

要输出 A[1:n] 的最优计算次序只需要调用 Traceback(1,n,s) 即可。

# ⑤ 完整程序 (Java)

整合一下上述代码段，将其写成一个完整的程序：

public class Matrix {

    private static int n = 6; // 表示一共 n 个矩阵
    private  int[] p; // 存储矩阵的行列数
    private  int[][] m; // 存储每个子问题的最优值(计算量)
    private  int[][] s; // 存储每个子问题的最优断开位置

    public Matrix(){
        p = new int[]{30, 35, 15, 5, 10, 20, 25};
        m = new int[n+1][n+1];
        s = new int[n+1][n+1];
    }

    // 核心算法（状态转移方程）
    public void MatixChain(){

        // m[i][i]只有一个矩阵，所以相乘次数为0，即 m[i][i] = 0;
        for(int i = 1; i <= n; i ++)
            m[i][i] = 0; 

        // r 表示矩阵链的长度（r 个矩阵相乘）
        for(int r = 2; r <= n; r ++){
            for(int i = 1; i <= n-r+1; i ++){
                // 以 i 为起始位置，j 为长度为 n 的矩阵链的末位
                int j = i + r - 1;
                // 将链 A[i:j] 划分为 A(i) * ( A[i+1:j] ) 
                m[i][j] = m[i+1][j] + p[i-1] * p[i] * p[j];
                s[i][j] = i; // 初始化断开点位置

                // 将链 A[i:j] 划分为 A[i:k] * A[k+1:j]
                for(int k = i + 1; k < j; k ++){
                    int temp = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
                    if(temp < m[i][j]){
                        m[i][j] = temp; // 更新最优值
                        s[i][j] = k; // 更新断开点位置
                    }
                }
            }
        }
    }

    // 返回 s 数组 i~j 范围内的最优值
    public void Traceback(int i, int j){
        if(i == j)
           return ;
        Traceback(i, s[i][j]);
        Traceback(s[i][j]+1, j);
        System.out.println("Multiply  A" + i + "," + s[i][j] + " and A" + (s[i][j] + 1) + "," + j);
    }

    public static void main(String[] args){
        Matrix matrix = new Matrix();
        matrix.MatixChain();
        matrix.Traceback(1, n);
    }
}

# 3. 动态规划算法的基本要素

⭐ 动态规划算法的有效性依赖于问题本身所具有的【两个重要性质】：

最优子结构
子问题重叠性质

众所周知，状态转移方程是 DP 系列最难的一步，本节还会给出写状态转移方程的套路模板 😃。

# ① 最优子结构

当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。

举个例子：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。

比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。

上述问题就符合最优子结构。比如你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案。

# ② 重叠子问题

在用递归算法自顶向下计算该问题时，每次产生的子问题并不总是新的问题，有些子问题被反复计算。以上面的矩阵连乘为例，我们直接使用递归计算 A[i:j] 的最小数乘次数：

// 递归求解矩阵连乘最少次数
public int RecurMatirxChain(int i, int j){
    if(i == j)
        return 0;
    int u = RecurMatirxChain(i,i) + RecurMatirxChain(i+1,j) + p[i-1] * p[i] * p[j];
    s[i][j] = i;
    for(int k = i + 1; k < j; k ++){
        int t = RecurMatirxChain(i,k) + RecurMatirxChain(k+1,j) + p[i-1] * p[k] * p[j];
        if(t < u){
            u = t;
            s[i][j] = k;
        }
    }
}

可以证明该算法的计算时间 T(n) 具有指数下界：

有两种方法可以解决重叠子问题带来的问题 👇

# Ⅰ 自底向上（动态规划）

如上面引例的解法，动态规划算法正是利用了这种子问题的重叠性质，对每个子问题只求解一次，然后按照递增（自底向上）的方式逐步将子问题的解存储在辅助表内，当再次需要解此问题时，查找该辅助表即可。

💡 自底向上：注意上图 3-2 的递归树（或者说图）。动态规划算法就是从问题规模最小的基本情况（base case）比如 A[2:2] 开始逐层往上推导，直到我们想要的上层答案比如 A[1:4]。这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

相比于直接递归的指数级时间复杂度，动态规划的主要计算量取决于程序中的三重循环，时间复杂度只有

# Ⅱ 自顶向下（备忘录法）

💉 备忘录方法是动态规划算法的变形。

当某个问题可以用动态规划法求解, 但二维数组中有相当一部分元素在整个计算中都不会被用到。因此，不需要以递推方式逐个计算二维数组中元素，而采用备忘录方法：

与动态规划算法一样，备忘录法需要使用辅助表存储已解决的子问题的答案。不同的是，动态规划算法是自底向上递归的，而备忘录法是自顶向下递归的。因此，备忘录法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以便需要时查看。

💡 自顶向下：注意上图 3-2 的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题向下逐渐分解规模，直到类似于 A[2: 2] 这种基本情况 (base case)，然后自底层逐层向上返回答案，这就叫「自顶向下」。

💧 备忘录方法为每个子问题建立一个记录项，并将其初始化为某个特殊的值，表示该子问题尚未求解。在递归的过程中，对每个待求的子问题，首先查找对应的记录项，若为初始值，则表示该子问题是第一次遇到，则计算出该子问题的解并存储在对应的记录项中，以便需要时查看。

以引例-矩阵连乘问题为例，备忘录方法的代码如下：

// 备忘录
public int MemoizeMatirxChain(int n, int[][] m, int[][] s){
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            m[i][j] = 0; // 初始化备忘录
        }
        return LookupChain(1, n);
    }
}

public int LookupChain(int i, int j){
    if(m[i][j] > 0)
        return m[i][j];
    if(i == j)
        return 0;
    int u = LookupChain(i,i) + LookupChain(i+1,j) + p[i-1] * p[i] * p[j];
    s[i][j] = i;
    for(int k = i + 1; k < j; k ++){
        int t = LookupChain(i,k) + LookupChain(k+1,j) + p[i-1] * p[k] * p[j];
        if(t < u){
            u = t;
            s[i][j] = k;
        }
    }
    m[i][j] = u; // 更新备忘录
    return u;
}

显然，大家也能看出来，😊 备忘录算法不过就是在直接递归算法的基础上加入了一个用来记忆的数组罢了。

对于上述代码，备忘录算法的时间复杂度和动态规划一样同为：共有个备忘录项 m[n][n]，这些记录项的初始化时间为，每个记录项值填入一次，共耗费时间，因此，备忘录算法填入个记录项总共耗费的计算时间。

# Ⅲ 两种方法的比较

一般来讲：

当一个问题的所有子问题都需要至少求解一次时，用动态规划算法比用备忘录方法好。
当部分子问题可不必求解时，用备忘录方法则比较有利，因此从其控制结构来说，该方法只解决那些确实需要求解的问题。

# ③ 状态转移方程

在实际的算法问题中，写出状态转移方程是最困难的，此处提供一个思维框架，辅助你思考状态转移方程：

👉 明确「状态」（根据最优子结构，状态就是原问题和子问题中会变化的变量）
👉 明确「选择」
👉 明确辅助表/数组/函数 DP Table 的含义（辅助表的参数就是状态转移中会变化的量，也就是上面说到的「状态」；辅助表表示的就是题目要求我们计算的量）
👉 明确 base case

⭐ 按上面的套路走，最后的结果就可以套这个框架：

// 初始化 base case
dp[0][0][...] = base
// 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

🚨🚨🚨 注意，一定要注意循环的顺序问题，下面这几张图画的简直不要太清晰，来源于 LeetCode liweiwei1419 (opens new window)：（这是大佬针对某个题目的讲解，大家忽略图中的错误和正确，只需要看填表顺序和对应的 for 循环就可以了，其中 i 是行的下标，j 是列的下标）

# 4. 不连续子序列问题

连续的子序列可以说是子数组，不连续的子序列问题显然比子数组问题要更困难一些。而且，子序列问题很可能涉及到两个字符串，比如让你求两个字符串的最长公共子序列，如果没有一定的处理经验，真的不容易想出来。所以此处就来扒一扒子序列问题的套路，其实只有两种模板。

1）第一种思路模板是一个一维的 dp 数组：

int n = array.length;
int[] dp = new int[n];

for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
        dp[i] = 最值(dp[i], dp[j] + ...)
    }
}

如下最长上升子序列问题

2）第二种思路模板是一个二维的 dp 数组：

int n = arr.length;
int[][] dp = new dp[n][n];

for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j++) {
        if (arr[i] == arr[j]) 
            dp[i][j] = dp[i][j] + ...
        else
            dp[i][j] = 最值(...)
    }
}

这种思路运用相对更多一些，尤其是涉及两个字符串/数组的子序列。本思路中 dp 数组含义又分为「只涉及一个字符串」和「涉及两个字符串」两种情况。

涉及两个字符串/数组时（比如最长公共子序列），dp 数组的含义如下：在子数组 arr1[0..i]和子数组arr2[0..j]中，我们要求的子序列长度为dp[i][j]。
只涉及一个字符串/数组时（比如最长回文子序列），dp 数组的含义如下：在子数组 array[i..j]中，我们要求的子序列的长度为dp[i][j]。

# 300. 最长上升子序列 LIS

300 - 最长上升子序列 — Medium

【问题描述】：

给定一个无序的整数数组，找到其中**最长上升子序列（Longest Increasing Subsequence）**的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

你算法的时间复杂度应该为 $O(n^2) $。

# Ⅰ 最优子结构

该问题符合最优子结构性质。以第 i 个数结尾的最长递增序列，一定包含以第 j 个数（j < i）结尾的最长递增序列

# Ⅱ 状态转移方程

🔸 首先明确状态：状态只有一个，就是「以第 i 个数结尾」。

🔸 明确选择：对于每个数字，选择有两个，就是「加入递增序列」或者「不加入递增序列」。

🔸 明确辅助表的定义：用辅助表表示状态，看看刚才找到的「状态」，只有一个，也就是说我们只需要一个一维dp[]数组。**dp[i]的定义如下：以下标为 i 的数结尾的最长递增子序列长度。**举个例子：

小牛肉说：dp[i] 你定义成以第 i 个数结尾也行，不过注意第 i 个数对应的数组下标是 i-1，你需要为辅助数组多开辟一个空间

根据这个定义，我们想求的最终答案就是dp[N]， N 为数组的最大下标。

🔸 最后明确基本情况 base case：以下标为 i 的数结尾的最长递增子序列长度至少是 1（因为子序列最少也要包含自己）。

⭐ OK，下面可以开始写状态转移方程（选择与状态的关系）：根据最优子结构性质，对于以第 i 个数结尾的最长递增子序列长度，一定包含以下标为 j 的数（j < i）结尾的最长递增序列。举个例子：假如我们想求 dp[5] 的值，也就是想求以 nums[5] 为结尾的最长递增子序列。nums[5] = 3

我们只要找到前面那些结尾比 3 小的最长递增子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一：

num[0] = 1 < 3, 则 dp[5] = dp[0] + 1 = 2
num[1] = 4 > 3, 不是以 nums[5] 结尾的递增子序列
num[2] = 3 = 3, 不是以 nums[5] 结尾的递增子序列
num[3] = 4 > 3, 不是以 nums[5] 结尾的递增子序列
num[4] = 2 < 3, 则 dp[5] = dp[4] + 1 = 3

从中选出最大的 dp[5] = 3，即以 nums[5] 为结尾的最长递增子序列长度为 3

用公式表示出来就是：💡 dp[i] = max(dp[i], dp[j] + 1) , j < i

# Ⅲ 实现状态转移方程

class Solution {
    public int lengthOfLIS(int[] nums) {

        int N = nums.length;
        int maxLength = 0; // 最长递增子序列长度

        // 辅助数组
        int[] dp = new int[N];

        // base case 初始化为 1
        Arrays.fill(dp, 1);

        // 状态转移方程
        for(int i = 0; i < N; i ++){
            for(int j = 0; j < i; j ++){
                if(nums[j] < nums[i])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        // 遍历 dp，查找最大值
        for(int i = 0; i < N; i ++){
            if(dp[i] > maxLength)
                maxLength = dp[i];   
        }

        return maxLength;
    }
}

各位可以看看这道题目，稍微有点变化，需要我们自己手动把它转换成最长上升子序列问题：1626. 无矛盾的最佳球队 — Medium (opens new window)

# 1143. 最长公共子序列 LCS

1143 - 最长公共子序列 — Medium

【问题描述】：

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列 (Longest Common Subsequence, LCS) 的长度。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

示例 2:

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。

示例 3:

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

下面按照动态规划算法的设计步骤来解决此问题 👇

# Ⅰ 最优子结构

由此可见，两个序列的最长公共子序列必然包含着这两个序列的前缀的最长公共子序列。举个例子：

比如：text1 = "abcde"，text2 = "abqcwe"

取 text1 前面某些部分 "abc"，取 text2 前面某个部分"abqc"，那么这两个子序列的最长公共子序列为 "abc"

显然 text1 和 text2 的最长公共子序列 "abce" 是包含 "abc" 的

# Ⅱ 状态转移方程

🔸 首先明确状态：状态有两个，就是「序列 X 的长度」和「序列 Y 的长度」。

🔸 明确选择：对于每个数字，选择有两个，就是「加入公共子序列」或者「不加入公共子序列」。

🔸 明确辅助表的定义：用辅助表表示状态，看看刚才找到的「状态」，有两个，也就是说我们需要一个二维dp数组，表示递增序列的长度。

🔸 最后明确基本情况 base case：当 i = 0 或 j = 0 时，和的最长公共子序列长度为 0。因为有一个字符串是空串，它们的最长公共子序列的长度显然应该是 0。

比如说对于字符串 b a b c d e 和字符串 a c e 构造一个辅助表：

其中，dp[i][j] 的含义是：对于 s1[1..i] 和 s2[1..j]，它们的最长公共子序列长度是 dp[i][j]。比如上图的例子，dp[2][4] 的含义就是：对于 "ac" 和 "babc"，它们的最长公共子序列长度是 2。 dp[0][3]=0 的含义是：对于字符串 "" 和 "bab"，其 LCS 的长度为 0。我们最终想得到的答案应该是 dp[3][6]。

⭐ OK，下面可以开始写状态转移方程（选择与状态的关系）：

// m 是第一个序列的长度，n 是第二个序列的长度
// 由于我们辅助表的第 0 行和第 0 列不用，所以需要 new int[m+1][n+1]
int[][] dp = new int[m+1][n+1];

# Ⅲ 实现状态转移方程

根据上面的状态转移方程，在计算 dp[i][j] 之前，我们需要先计算 dp[i-1][j-1] 和 dp[i-1][j] 以及 dp[i][j-1]，从图中可以看出，我们直接从 0 开始顺序遍历即可保证计算顺序。

计算最长公共子序列的长度：

/**
 * @param m 序列 x 的个数：X_1, X_2 ...  X_m
 * @param n 序列 y 的个数：Y_1, Y_2 ...  Y_n
 * @param x 序列 x
 * @param y 序列 y
 * @param dp dp[i][j] 存储 X_i 和 Y_j 的最长公共子序列的长度
 * @param b b[i][j] 记录 dp[i][j] 的值是由哪个子问题的解得到的
 */
public void LCSlength(int m, int n, char[] x, char[] y, int[][] dp, int[][] b){

    // base case
    for(int i = 1; i <= m; i ++){
        dp[i][0] = 0;
    }
    for(int i = 1; i <= n; i++){
        dp[0][i] = 0;
    }

    // 状态转移方程
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            // 加入公共子序列
            // 注意一下这个地方, 因为我们在辅助表的外围加了一圈 0
            // 所以对应于字符串的下标需要相应的 - 1，看一下上面的图就明白了
            if(x[i-1] == y[j-1]){ 
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            // 不加入公共子序列的两种情况
            else 
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
}

💡 上面两段 base case 的过程其实是可以省略的，因为 new 的时候就已经初始成 0 了。

⏰ 上述代码的时间复杂度主要在于两个 for 循环，因此算法 LCSLength 时间复杂度为 O(mn)

# Ⅳ 状态压缩

如果只需要计算最长公共子序列的长度，则上述算法还能够继续优化。我们在计算 c[i][j] 的时候，只用到数组 c 的第 i 行和第 i-1 行，只需要用两行的数组空间就可以计算出最长公共子序列的长度。

💡 这就是状态压缩的技巧。也就是说我们发现每次状态转移只需要辅助表 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据，从而实现进一步减少空间复杂度

准备几个变量：

last:表示是当前 dp[j](dp[i][j]) 左上角的数，相当于 dp[i-1][j-1] ,初始化的时候为 0
temp:表示是当前 dp[j](dp[i][j]) 正上方的数，相当于 dp[i- 1][j]
dp[j-1]:表示是当前 dp[j](dp[i][j]) 左边的数，相当于 dp[i][j-1]
每一轮结束后，last的值都向前滚动一个，变成正上方的数，也就是 temp

之前的状态转移方程为：

dp[i][j] = 0 / dp[i-1][j-1] + 1 / max{ dp[i][j-1] | dp[i-1][j] }

转换为：

dp[j] = 0 / last + 1 / max{ dp[j-1] | temp }

代码如下：

// 计算最长公共子序列的长度
public void LCSlength(char[] x, char[] y){
    int m = x.length;
    int n = y.length;
    int[] dp = new int[n+1]; // 辅助数组
    int temp = 0;
    for(int i = 1; i <= m; i ++){
        int last = 0;
        for(int j = 1; j <= n; j++){
            temp = dp[j];
            if(x.charAt(i-1) == y.charAt(j-1))
                dp[j] = last + 1;
            else if(temp >= dp[j-1])
                dp[j] = temp;
            else
                dp[j] = dp[j-1];
            last = temp;
        }
    }
    return dp[n];
}

空间复杂度降至 O(min{m,n})

# 516. 最长回文子序列 LPS

516 - 最长回文子序列 — Medium

【问题描述】：

给定一个字符串 s ，找到其中最长的回文子序列（ Longest Palindromic Subsequence），并返回该序列的长度。可以假设 s 的最大长度为 1000。

示例 1:

输入: "bbbab"
输出: 4
一个可能的最长回文子序列为 "bbbb"。

示例 2:

输入: "cbbd"
输出: 2
一个可能的最长回文子序列为 "bb"。

# Ⅰ 最优子结构

该题符合最优子结构的性质：假设要求下标 i 和 j 之间的最长回文子序列长度 A，已知下标 i+1 和 j-1 之间的最长回文子序列长度 B。A 一定包含或者等于 B。如果 s[i] 和 s[j] 相等，那么 A = B + 2：

如果 s[i] 和 s[j] 不相等，说明他俩不可能同时出现在 s[i : j] 的最长回文序列中，那么将它们分别加入 s[i+1 : j-1] 中，看看哪个子串产生的回文子序列更长即可

# Ⅱ 状态转移方程

🔸 首先明确状态：状态有两个，就是「待求序列的下标上限 i」和「待求序列的下标下限 j」。

🔸 明确选择：对于每个数字，选择有两个，就是「加入回文子序列」或者「不加入回文子序列」。

🔸 明确辅助表的定义：用辅助表表示状态，看看刚才找到的「状态」，有两个，也就是说我们需要一个二维dp数组，其中一维表示待求序列的下标上限，另一维表示表示待求序列的下标下限。**dp[i][j]的定义如下：在子串s[i..j]中，最长回文子序列的长度为dp[i][j]。**根据这个定义，我们想求的最终答案就是dp[0][N-1]， N 为数组的长度。

🔸 最后明确基本情况 base case：如果只有一个字符，显然最长回文子序列长度是 1，也就是dp[i][j] = 1,(i == j)。并且对于那些i > j的位置，不存在子序列，也就是说辅助表 dp 的对角线的左边都是不需要使用的：

⭐ OK，下面可以开始写状态转移方程（选择与状态的关系）：根据最优子结构性质：

dp[i][j] = dp[i+1][j-1] + 2, s[i] = s[j]
dp[i][j] = max( dp[i][j-1], dp[i+1][j]), s[i] ≠ s[j]

# Ⅲ 实现状态转移方程

根据状态转移方程，在计算 dp[i][j] 之前，我们需要计算 dp[i][j-1] 和 dp[i+1][j] 以及 dp[i+1][j-1]，从图中可以看出，我们不能从 0 开始顺序遍历，只能斜着遍历或者反着遍历以保证计算顺序：

我选择反向遍历：i 从最后一个字符开始往前遍历，j 从 i + 1 开始往后遍历

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        // base case
        for(int i = 0; i < n; i ++)
            dp[i][i] = 1;

        // 状态转移方程
        for(int i = n - 1; i >= 0; i --){
            for(int j = i + 1; j < n; j ++){
                if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i+1][j-1] + 2;
                else
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][n-1];
    }
}

# 5. 背包问题 Knapsack problem

# ① 0-1 背包问题

【问题描述】：给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性，且每个物品只有一件。其中第 i 个物品的重量为 w[i]，价值为 v[i]，现在让你用这个背包装物品，且每个物品只能使用一次，最多能装的价值是多少？

举个简单的例子，输入如下：

N = 3, W = 4
w = [2, 1, 3]
v = [4, 2, 3]

算法返回 6，选择前两件物品装进背包，总重量 3 小于 W，可以获得最大价值 6。

题目就是这么简单，一个典型的动态规划问题。这个题目中的物品不可以分割，要么装进包里，要么不装，不能说切成两块装一半。这就是 0-1 背包这个名词的来历。

# Ⅰ 最优子结构

该问题符合最优子结构性质：设是该问题的一个最优解，则是下面相应子问题的一个最优解：

# Ⅱ 状态转移方程

🔸 按照套路来，首先明确状态：子问题中在不断变化的变量，就是「背包的容量」和「可选择的物品」。

🔸 明确选择：对于每件物品，你能选择什么？选择也有两个，就是「装进背包 1」或者「不装进背包 0」。

🔸 明确辅助表的定义：用辅助表表示状态，看看刚才找到的「状态」，有两个，也就是说我们需要一个二维dp数组，一维表示可选择的物品，一维表示背包的容量。dp[i][w]的定义如下：对于前i个物品，当前背包的容量为w (还能装入 w 重量的物品)，这种情况下可以装的最大价值是dp[i][w]。 比如说，如果 dp[3][5] = 6，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。根据这个定义，我们想求的最终答案就是dp[N][W]。

🔸 最后明确基本情况 base case：

背包容量为空时（N=0），能装的最大价值为 0 即 dp[0][..] = 0
物品容量为空时（W=0），能装的最大价值为 0 即 dp[..][0] = 0

💡 在 Java 中，dp = new int[N+1][W+1]; 会将 dp 数组全部初始化成 0，所以 base case 不必在代码中手动实现~

⭐ OK，下面可以开始写状态转移方程（选择与状态的关系）：对于前i个物品，当前背包的容量为w时，这种情况下可以装下的最大价值是dp[i][w]：

当前背包容量装不下第 i个物品，只能选择不装入背包，那么很显然，最大价值dp[i][w]应该等于dp[i-1][w]。
当前背包还有容量：
- 如果你没有把这第 i个物品装入背包，那么很显然，最大价值dp[i][w]应该等于dp[i-1][w]。
- 如果你把这第 i 个物品装入了背包，那么dp[i][w]应该等于dp[i-1][w-w[i-1]] + v[i-1]。
  
  🚨 注意 i 的取值范围为 1~N，从 1 开始计数，对应于 w[]和 v[] 数组的下标应为 i - 1

分析结束，接下来套模板即可 👇

# Ⅲ 实现状态转移方程

根据上面的状态转移方程，在计算 dp[i][w] 之前，我们需要先计算 dp[i-1][w] 和 dp[i-1][w-w[i-1]] ，直接从 0 开始顺序遍历即可保证计算顺序。

private int[] weight; // 物品对应重量 
private int[] value; // 物品对应价值

/**
 * 返回最大价值
 * @param W 背包最大承受的物品总重量
 * @param N 背包最多承受的物品总数量
 * @return
 */
public int Knapsack(int N, int W){
    int[][] dp = new int[N+1][W+1];
    for(int i = 1; i <= N; i ++){ // 状态 1：可选择的物品
        for(int w = 1; w <= W; w ++){ // 状态 2：背包容量
            // 挑选最佳选择存入辅助表
            if(w - weight[i-1] < 0) // 当前背包容量装不下，只能选择不装入背包
                dp[i][w] = dp[i-1][w];
            else{ // 装入或者不装入背包，择优
                dp[i][w] = Math.max(dp[i-1][w-weight[i-1]] + value[i-1], dp[i-1][w]);
            }
        }
    }
    return dp[N][W];
}

🚨 注意，我们传入的 N 必须要和物品的数量一致。

# Ⅳ 状态压缩

根据上面的状态转移方程，在计算 dp[i][w] 之前，我们只需要计算 dp[i-1][..] 的值，因此我们可以将辅助数组 dp 从二维降到一维，去掉第 1 维（即 i 的那一维），节约空间复杂度。并且由判断条件可知只有在 w - weight[i-1] >= 0 时，才会考虑是否将该物品加入背包。⭐ 为保证每个物品只能使用一次，我们倒序遍历所有 w 的值，类似于递归的方式，这样在更新 dp[w] 的时候，dp[w-weight[i-1]] 的值尚未被修改，就不会出现一个物品重复使用的问题。

此处辅助表 dp[w] 的定义相当于：对于容量为 w 的背包，能够装的最大价值 dp[w]

💡 所以我们只需要修改一下判断条件，将 w 从 W 开始依次递减，将代码压缩至一行：

public int Knapsack(int N, int W){
    int dp = new int[W+1];
    for(int i = 1; i <= N; i ++){
        for(int w = W; w - weight[i-1] >= 0; w --)
            dp[w] = Math.max(dp[w-weight[i-1]] + value[i-1], dp[w]);
    }
    return dp[W];
}

⭐ 这里解释一下为什么要倒序枚举（从大重量背包到小重量）：

因为 w > w-weight[i-1]，所以第 i 次循环中，执行背包容量为 j 时，容量为 w-weight[i-1] 的背包已经计算过了，如果使用正序遍历，显然某些物品会被重复使用。

# 📜 LeetCode

🎯 题解	🎲 难度
474 - 一和零	👻
416 - 分割等和子集	👻

# ② 完全背包问题

【问题描述】：有 N 种物品和一个容量为 W 的背包，每种物品都有无限个，第 i 种物品的价值为 v[i]，重量为 w[i]，求解：选哪些物品放入背包，可使得背包中的价值最大，并且不超过背包容量。

💡 显然，和 0-1 背包问题最大的不同点就在于：完全背包问题中的物品拥有无限个

我们直接以 LeetCode 中的实例分析：518. 零钱兑换 II (opens new window)

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

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

示例 3:

输入: amount = 10, coins = [10] 
输出: 1

⭐ 我们可以把这个问题转化为背包问题的描述形式：有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？

# Ⅰ 最优子结构

该题满足最优子结构：比如说对于第 i 个硬币(下标 i-1，如果我们将其装入背包恰好能够装满，也就意味着，在装入第 i 个硬币之前，背包的重量应该等于 amount-coins[i-1]，再加上第 i 个硬币就能装满背包。

# Ⅱ 状态转移方程

🔸 按照套路来，首先明确状态：同 0-1 背包问题，状态有两个「背包的容量（总金额）」和「可选择的物品（硬币）」。

🔸 明确选择：同 0-1 背包问题，选择也有两个，就是「装进背包」或者「不装进背包」。

🔸 明确辅助表的定义：用辅助表表示状态，看看刚才找到的「状态」，有两个，也就是说我们需要一个二维dp数组，一维表示可选择的物品，一维表示背包的容量。dp[i][j]的定义如下：对于前i个物品，当前背包的容量为j (还能装入 j 重量的物品)，有 dp[i][j] 种方法可以装满背包。 比如说，如果 dp[3][5] = 6，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，有 6 种方法可以装满背包。根据这个定义，我们想求的最终答案就是dp[coins.length][amount]。

🔸 最后明确基本情况 base case：

硬币数量为空时，无法凑出任何金额，即 dp[0][..] = 0
背包容量为空时，只有一种装法即不装入任何硬币，即 dp[..][0] = 1

💡 在 Java 中，dp = new int[..][..]; 会将 dp 数组全部初始化成 0，所以 base case 中的 dp[0][..] = 0 不必在代码中手动实现~

⭐ OK，下面可以开始写状态转移方程（选择与状态的关系）：对于前i个物品，当前背包的容量为j (还能装入 j 重量的物品)，有 dp[i][j] 种方法可以装满背包：

背包容量不足以装入第 i 个物品，只能选择不装入，即dp[i][j] 应该等于 dp[i-1][j]
背包容量足够装入第 i 个物品：
- 如果你没有把这第 i个物品（下标 i-1 ）装入背包，那么很显然，dp[i][j] 应该等于 dp[i-1][j]。
- 如果你把这第 i 个物品装入了背包，那么dp[i][j]应该等于dp[i][j-coins[i-1]]。
  
  🚨 注意这个地方和 0-1 背包不一样，并不是 dp[i-1][j-coins[i-1]] 而是 dp[i][j-coins[i-1]]。
  
  首先，如果将第 i 个硬币（面值 coins[i-1]）装入背包，等价于先凑出金额 j-coins[i-1] 再加上第 i 个硬币即可。由于硬币个数是无限的，加入第 i 个硬币后，它不仅可以放在最后和 j-coins[i-1] 凑成金额 j，还可以用来凑金额 j-coins[i-1]。
  
  也就是说，加入第 i 个硬币后，能够正好凑出金额 j 的方法数不是 dp[i-1][j-coins[i-1]] 而是 dp[i][j-coins[i-1]]

🚨 需要额外注意的是：题目中要求的是总共有多少种解法，因此应该将装入第 i 个物品和不装入第 i 个物品的解法数相加起来。

# Ⅲ 实现状态转移方程

class Solution {
    public int change(int amount, int[] coins) {
        int len = coins.length;

        int[][] dp = new int[len+1][amount+1];

        // base case
        for(int i = 0; i <= len; i ++){
            dp[i][0] = 1;
        }

        for(int i = 1; i <= len; i ++){
            for(int j = 1; j <= amount; j ++){
                // 剩余总金额小于当前硬币的面值，无法装入该硬币
                if(coins[i-1] > j)
                    dp[i][j] = dp[i-1][j];
                else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }
            }
        }

        return dp[len][amount];
    }
}

# Ⅳ 状态压缩

与上述 0-1 背包的优化算法相反，我们正序遍历 j （即循环条件不变），正好可以实现每种物品的无限使用，即相当于每种物品有无限个：

此处辅助表 dp[j] 的定义相当于：对于容量为 j 的背包（总金额），总共有 dp[j] 种方法能够恰好装满

class Solution {
    public int change(int amount, int[] coins) {
        int len = coins.length;

        int[] dp = new int[amount+1];

        // base case
        dp[0] = 1;


        for(int i = 1; i <= len; i ++){
            for (int j = 1; j <= amount; j++)
                if (j - coins[i-1] >= 0)
                    dp[j] = dp[j] + dp[j-coins[i-1]];
        }



        return dp[amount];
    }
}

# 📜 LeetCode

🎯 题解	🎲 难度
518 - 零钱兑换 II	👻
322 - 零钱兑换	👻

# ③ 带顺序的完全背包问题

以这个题目为例：377. 组合总和 Ⅳ (opens new window)

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

⭐ 翻译成背包问题的语法就是：有一个背包，最大容量为 target，有一系列物品 nums，每个物品的重量为 nums[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满。注意物品装入顺序不同的方法被视为不同的方法

这类问题有个小坑，就是只能使用一维的辅助数组，因为选出来的物品并不影响后续取哪个物品。即我们上述所说的二维辅助数组的第一维（可选择的物品）是无法使用的。这样也好，直接套状态压缩后的模板吧 😂

和上述完全背包问题的代码基本完全一致，🚨 不过由于涉及到顺序问题，所以需要将对于物品的循环放在内循环：

for(int j = 1; j <= target; j ++){ // 对容量的循环
    for(int i = 1; i <= len; i ++){ // 对物品的循环

此处的辅助表 dp[i] 理解为：对于容量为 i 的背包，有 dp[i] 种方法装满。

OK，其余的直接抄代码就行了 😃

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int len = nums.length;

        int[] dp = new int[target+1];

        // base case
        // target = 0，只有一种方案即一个数也不选 dp[0] = 1
        dp[0] = 1;


        for(int j = 1; j <= target; j ++){
            for(int i = 1; i <= len; i ++){
                if(nums[i-1] <= j)
                    dp[j] = dp[j] + dp[j-nums[i-1]];
            }
        }

        return dp[target];
    }
}

# 📜 LeetCode

🎯 题解	🎲 难度
139 - 单词拆分	👻
377 - 组合总和 Ⅳ	👻

# 6. 股票交易问题

# ① 最多允许 K 笔交易

先说这个题目 👽 188 - 买卖股票的最佳时机 IV，下面所有题目都是这个题目的简化。

【题目描述】：给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2:

输入: prices: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

按照套路来：

🔸 状态：状态就是问题中会变化的变量，【天数】，【允许交易的最大次数】，【当前股票的持有情况】

🔸 选择：每天都有三种「选择」，【买入】、【卖出】、【无操作】，我们用 buy, sell, rest 表示这三种选择。但问题是，并不是每天都可以任意选择这三种选择的，因为 sell 必须在 buy 之后，buy 必须在 sell 之后。那么 rest 操作还应该分两种状态，一种是 buy 之后的 rest（持有了股票），一种是 sell 之后的 rest（没有持有股票）。而且别忘了，我们还有交易次数 k 的限制，就是说你 buy 还只能在 k > 0 的前提下操作。

🔸 辅助表定义：定义一个三维辅助表 dp[i][k][s] 表示到第 i 天为止（对应数组下标 i-1)，至多还能进行 k 次交易，s 表示现在手上是否持有股票（1 表示持有股票，0 表示不持有），能够获得的最大利润为 dp[i][k][s] 。

⭐ 根据定义，我们的最终目标是 dp[n][K][0]， n 表示 prices数组的长度，即到最后一天为止，最多允许 K 次交易，最多获得 dp[n][K][0] 的利润。读者可能问为什么不是 dp[n][K][1]？因为 [1] 代表手上还持有股票，[0] 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者。

🔸 状态转移方程：到第 i 天为止（对应数组下标 i-1)，至多还能进行 k 次交易，s 表示现在手上是否持有股票（1 表示持有股票，0 表示不持有），能够获得的最大利润为 dp[i][k][s] :

通过这个图可以很清楚地看到，每种状态（0 和 1）是如何转移而来的。根据这个图，我们来写一下状态转移方程：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i-1])

解释：今天我没有持有股票，有两种可能：要么是我昨天就没有持有，然后今天选择不做任何操作 rest，所以我今天还是没有持有；要么是我昨天持有股票，但是今天我售出了 sell，所以我今天没有持有股票了，并且获得了今天当天的利润 price[i-1]。
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i-1])

解释：今天我持有着股票，有两种可能：要么我昨天就持有着股票，然后今天选择不做任何操作 rest，所以我今天还持有着股票；要么我昨天本没有持有，但今天我选择买入 buy，所以今天我就持有股票了，并且获得的利润相应减少了。注意我们记买入操作为一次交易的开始，即 k - 1。也可在售出的时候再 k - 1

🔸 base case：

dp[..][0][0] = 0 可不写，Java 中 new int 会自动初始化成 0

解释：因为 k 表示允许交易的最大次数，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[..][0][1] = -infinity

解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。
dp[0][..][0] = 0 可不写

解释：因为 [i] 表示是到第 i 天为止，对应 prices数组下标 i-1，所以 i = 0 意味着还没有开始，这时候的利润当然是 0 。
dp[0][..][1] = -infinity

解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。

🚨 注意这里需要考虑传入的 K 值过大的问题，会导致 dp 数组太大超出内存。其实，一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 K 应该不超过 n/2，如果超过，就没有约束作用了，相当于 K = +infinity：

class Solution {
    public int maxProfit(int K, int[] prices) {
        int len = prices.length;
        if(len <= 0)
            return 0;
        // 如果 K 超过 len/2，相当于无限制
        if(K > len/2)
            return maxProfitWithInfinity(prices);

        int[][][] dp = new int[len+1][K + 1][2];

        // base case
        for(int i = 1; i <= len; i ++)
            dp[i][0][1] = -0x3f3f3f3f;
        for(int i = 1; i <= K; i ++)
            dp[0][i][1] = -0x3f3f3f3f;

        for (int i = 1; i <= len; i++){
            for(int k = 1; k <= K; k ++){
                dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i-1]);
                dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i-1]);
            }
        }

        return dp[len][K][0];
    }

    // k = +infinity
    public int maxProfitWithInfinity(int[] prices) {
        int len = prices.length;
        if(len <= 0)
            return 0;

        int[] dp = new int[2];

        // base case
        dp[0] = 0;
        dp[1] = -0x3f3f3f3f;

        // 状态转移方程
        for(int i = 1; i <= len; i ++){
            dp[0] = Math.max(dp[0], dp[1] + prices[i-1]);
            dp[1] =  Math.max(dp[1], dp[0] - prices[i-1]);
        }

        return dp[0];
    }
}

关于上述 k = +infinity 的代码兄弟们可以往下看详解

# ② 最多允许两笔交易

👽 123 - 买卖股票的最佳时机 III — Hard

k = 2

原始的动态转移方程，没有可化简的地方

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i-1])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i-1])

base case：

dp[..][0][0] = 0
dp[..][0][1] = -infinity
dp[0][..][0] = 0
dp[0][..][1] = -infinity

显然，K 无法消除，我们需要两个循环：

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len <= 0)
            return 0;

        int K = 2;

        int[][][] dp = new int[len+1][K + 1][2];

        // base case
        for(int i = 1; i <= len; i ++)
            dp[i][0][1] = -0x3f3f3f3f;
        for(int i = 1; i <= K; i ++)
            dp[0][i][1] = -0x3f3f3f3f;

        for (int i = 1; i <= len; i++){
            for(int k = 1; k <= 2; k ++){
                dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i-1]);
                dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i-1]);
            }
        }

        return dp[len][K][0];
    }
}

# ③ 最多允许一笔交易

😎 121 - 买卖股票的最佳时机

🔈 K = 1

直接套状态转移方程：

dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i-1])
dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i-1]) = max(dp[i-1][1][1], - prices[i-1])

可以发现，现在 k 都是 1 并且不会发生改变，所以可以去掉这一维：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1])
dp[i][1] = max(dp[i-1][1], - prices[i-1])

base case：

dp[0][0] = 0
dp[0][1] = -infinity

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len <= 0)
            return 0;

        int[][] dp = new int[len+1][2];

        // base case
        dp[0][0] = 0; // 可不写
        dp[0][1] = -0x3f3f3f3f;

        // 状态转移方程
        for(int i = 1; i <= len; i ++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
            dp[i][1] = Math.max(dp[i-1][1], -prices[i-1]);
        }

        return dp[len][0];
    }
}

🚜 【状态压缩】：显然，dp[i] 只和 dp[i-1] 有关，我们可以去除 i 的那一维，只用一维辅助表：

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len <= 0)
            return 0;

        int[] dp = new int[2];

        // base case
        dp[0] = 0; // 可不写
        dp[1] = -0x3f3f3f3f;

        // 状态转移方程
        for(int i = 1; i <= len; i ++){
            dp[0] = Math.max(dp[0], dp[1] + prices[i-1]);
            dp[1] = Math.max(dp[1], -prices[i-1]);
        }

        return dp[0];
    }
}

这么简洁的代码上来就直接写谁能写出来 😒

# ④ 可无限次交易

😎 122 - 买卖股票的最佳时机 II

🔈 k = +infinity

如果 k 为正无穷，那么就可以认为 k 和 k - 1 是一样的，套状态转移方程：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i-1])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i-1])

由上式可发现，k 不会发生改变，可以去除该维度：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1])

base case：

dp[0][0] = 0
dp[0][1] = -infinity

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len <= 0)
            return 0;

        int[][] dp = new int[len+1][2];

        // base case
        dp[0][0] = 0;
        dp[0][1] = -0x3f3f3f3f;

        // 状态转移方程
        for(int i = 1; i <= len; i ++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
            dp[i][1] =  Math.max(dp[i-1][1], dp[i-1][0] - prices[i-1]);
        }

        return dp[len][0];
    }
}

🚜 【状态压缩】：显然，dp[i] 只和 dp[i-1] 有关，我们可以去除 i 的那一维，只用一维辅助表：

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len <= 0)
            return 0;

        int[] dp = new int[2];

        // base case
        dp[0] = 0;
        dp[1] = -0x3f3f3f3f;

        // 状态转移方程
        for(int i = 1; i <= len; i ++){
            dp[0] = Math.max(dp[0], dp[1] + prices[i-1]);
            dp[1] =  Math.max(dp[1], dp[0] - prices[i-1]);
        }

        return dp[0];
    }
}

# ⑤ 需要冷冻期的股票交易

👻 309 - 最佳买卖股票时机含冷冻期

k = +infinity with cooldown

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。只要把这个特点融入上一题可无限次交易的状态转移方程即可：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i-1])

解释：第 i 天我们持有股票，其中一种可能情况是我们之前不持有股票，在第 i 天选择买入股票，选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1。因为如果第 i 天可以进行买入操作的话，那么由于冷冻期的存在，第 i-1 天一定是没有进行卖出操作的。

注意到我们的代码中会出现 i-2,而 i 是从 i = 1 开始的，-1 会发生越界。我们可以把 dp[1][0] 和 dp[1][1] 放在循环外面，使循环从 i = 2 开始

base case：

dp[0][0] = 0
dp[0][1] = -infinity
➕ dp[1][0] = max(dp[0][0], dp[0][1] + prices[0]) = 0
➕ dp[1][1] = max(dp[0][1], dp[-1][0] - prices[0]) = - prices[0]

dp[1][1] 表示到第一天为止，手上持有股票，所以只有当天买入，则最大利润为 - prices[0]

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len <= 0)
            return 0;

        int[][] dp = new int[len+1][2];

        // base case
        dp[0][0] = 0;
        dp[0][1] = -0x3f3f3f3f;
        dp[1][0] = 0;
        dp[1][1] = -prices[0];

        // 状态转移方程
        for(int i = 2; i <= len; i ++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
            dp[i][1] =  Math.max(dp[i-1][1], dp[i-2][0] - prices[i-1]);
        }

        return dp[len][0];
    }
}

🚜 【状态压缩】：显然，dp[i] 只和 dp[i-1] 以及 dp[i-2] 有关，我们可以去除 i 的那一维，只用一维辅助表：

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len <= 0)
            return 0;

        int[] dp = new int[2];

        // base case
        dp[0] = 0;
        dp[1] = -0x3f3f3f3f;

        int pre = 0; // 代表 dp[i-2][0]

        // 状态转移方程
        for(int i = 1; i <= len; i ++){
            int temp = dp[0];
            dp[0] = Math.max(dp[0], dp[1] + prices[i-1]);
            dp[1] = Math.max(dp[1], pre - prices[i-1]);
            pre = temp;
        }

        return dp[0];
    }
}

# ⑥ 需要交易费用的股票交易

👻 714 - 买卖股票的最佳时机含手续费

k = +infinity with fee

每次交易要支付手续费，只要把手续费从利润中减去即可。改写方程：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1] - fee)

解释：相当于买入股票的价格升高了（买入股票的时候为此次交易支付手续费）。

在第一个式子里减也是一样的，相当于卖出股票的价格减小了（卖出股票的时候为此次交易支付手续费）。

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int len = prices.length;
        if(len <= 0)
            return 0;

        int[][] dp = new int[len+1][2];

        // base case
        dp[0][0] = 0;
        dp[0][1] = -0x3f3f3f3f;

        // 状态转移方程
        for(int i = 1; i <= len; i ++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
            dp[i][1] =  Math.max(dp[i-1][1], dp[i-1][0] - prices[i-1] - fee);
        }

        return dp[len][0];
    }
}

🚜 【状态压缩】：显然，dp[i] 只和 dp[i-1] 以及 dp[i-2] 有关，我们可以去除 i 的那一维，只用一维辅助表：

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int len = prices.length;
        if(len <= 0)
            return 0;

        int[] dp = new int[2];

        // base case
        dp[0] = 0;
        dp[1] = -0x3f3f3f3f;

        // 状态转移方程
        for(int i = 1; i <= len; i ++){
            dp[0] = Math.max(dp[0], dp[1] + prices[i-1]);
            dp[1] =  Math.max(dp[1], dp[0] - prices[i-1] - fee);
        }

        return dp[0];
    }
}

# 📜 LeetCode

🎯 题解	🎲 难度
121 - 买卖股票的最佳时机	😎
122 - 买卖股票的最佳时机 II	😎
714 - 买卖股票的最佳时机含手续费	👻
309 - 最佳买卖股票时机含冷冻期	👻
123 - 买卖股票的最佳时机 III	👽
188 - 买卖股票的最佳时机 IV	👽

# 7. 其他类型

# 718. 最长重复子数组

718. 最长重复子数组 — Medium (opens new window)

【题目描述】给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：

输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。

【解题思路】dp[i][j]：表示第一个数组 A 前 i 个元素和数组 B 前 j 个元素组成的最长公共子数组的长度。

若当前两个元素值相同，即 A[i] == B[j]，则说明当前元素可以构成公共子数组，所以还要加上它们的前一个元素构成的最长公共子数组的长度(在原来的基础上加 1)，此时状态转移方程：dp[i][j] = dp[i - 1][j - 1] + 1。
若当前两个元素值不同，即 A[i] != B[j]，则说明当前元素无法构成公共子数组(就是：当前元素不能成为公共子数组里的一员)。因为公共子数组必须是连续的，而此时的元素值不同，相当于直接断开了，此时状态转移方程：dp[i][j] = 0。

本题与最长公共子序列 LIS 不同，子序列不一定都是连续的，只要前面有相同的子序列，哪怕当前比较的字符不一样，那么当前字符串之前的子序列也不会为 0。而子串(子数组)是连续的，若当前比较的字符不相同，则当前位置的最长公共子数组(子串)的长度为 0，即 dp[i][j] = 0。

class Solution {
    public int findLength(int[] A, int[] B) {
        // dp[i][j] 表示 A 的前 i 个数和 B 的前 j 个数的最长子数组长度
        int[][] dp = new int[A.length+1][B.length+1];

        // base case

        int res = Integer.MIN_VALUE;
        // 状态转移方程
        for (int i = 1; i <= A.length; i ++) {
            for (int j = 1; j <= B.length; j ++) {
                if (A[i-1] == B[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else {
                    dp[i][j] = 0;
                }
                res = Math.max(res, dp[i][j]);
            }
        }

        return res;
    }
}

# 5. 最长回文子串

5. 最长回文子串 — Medium (opens new window)

【题目描述】给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

示例 3：

输入：s = "a"
输出："a"

示例 4：

输入：s = "ac"
输出："a"

【解题思路】和最长回文子序列不同，这个题目需要连续的子串。（注意此题的循环顺序）

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len <= 1) {
            return s;
        }

        // dp[i][j] 表示 s[i] 到 s[j] 是否是回文子串
        boolean[][] dp = new boolean[len][len];

        // base case
        for (int i = 0; i < len; i ++) {
            dp[i][i] = true;
        }

        int maxLen = 1; // 最长回文子串的长度
        int start = 0; // 最长回文子串的起始下标

        for (int j = 1; j < len; j ++) {
            for (int i = j-1; i >= 0; i --) {
                if (s.charAt(i) == s.charAt(j)) {
                    // 如果 s[i] 和 s[j] 之间只有一个字符或者没有字符,则 s[i:j] 为回文
                    if (j - i <= 2) {
                        dp[i][j] = true;                      
                    }
                    else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                else {
                    dp[i][j] = false;
                }

                // 记录最长回文子串的长度和起始位置
                if (dp[i][j]) {
                    int curLen = j - i + 1;
                    if (maxLen < curLen) {
                        maxLen = curLen;
                        start = i;
                    }
                }
            }
        }

        // 获取最长回文子串
        return s.substring(start, start + maxLen);
    }
}

# 343. 整数拆分

343. 整数拆分 (opens new window)

【题目描述】给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

【解题思路】辅助数组 dp[n+1]：dp[i] 表示对于将 i 拆分为至少两个正整数的和，这些整数最大乘积

状态转移方程：dp[i] = Math.max((i-j) * j , dp[i-j] * j)

将 i 拆分成 j 和 i-j 的和，且 i-j 不再拆分成多个正整数：dp[i] = (i-j) * j
将 i 拆分成 j 和 i-j 的和，且 i-j 继续拆分：dp[i] = dp[i-j] * j

class Solution {
    public int integerBreak(int n) {

        // dp[i] 表示对于将 i 拆分为至少两个正整数的和，这些整数最大乘积
        int[] dp = new int[n+1];

        // base case
        dp[2] = 1;

        for (int i = 3; i <= n; i ++) {
            int temp = 0;
            for (int j = 1; j < i; j ++) {
                temp = Math.max(temp, Math.max((i-j) * j , dp[i-j] * j));
            }
            dp[i] = temp;
        }

        return dp[n];
    }
}

# 剑指 Offer 60. n 个骰子的点数

剑指 Offer 60. n个骰子的点数 — Medium (opens new window)

【题目描述】把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例 1:

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

示例 2:

输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

【解题思路】动态规划

辅助数组：dp[i][j] 表示把 i 个骰子扔在地上, 所有骰子朝上一面的点数之和为 j 的次数
状态转移方程：如果把 i 个骰子扔在地上, 所有骰子朝上一面的点数之和为 j。相当于当前骰子朝上一面的点数为 cur（cur 可以是从 1 到 6）, 前面 i-1 个骰子的点数之和为 j-cur。即 dp[i][j] += dp[i-1][j-cur];

class Solution {
    public double[] dicesProbability(int n) {

        // dp[i][j] 表示把 i 个骰子扔在地上, 所有骰子朝上一面的点数之和为 j 的次数
        int[][] dp = new int[n+1][n*6 + 1];

        // base case: 只有一个骰子
        for (int i = 1; i <= 6; i ++) {
            dp[1][i] = 1;
        }

        for (int i = 2; i <= n; i ++) { // 骰子的个数
            for (int j = i; j <= i*6; j ++) { // 总共 i 个骰子朝上一面的点数之和
                for (int cur = 1; cur <= 6; cur ++) { // 当前骰子朝上一面的点数
                    if (cur >= j) {
                        // 当前骰子朝上一面的点数大于等于所有骰子朝上一面的点数之和，直接 break
                        break;
                    }
                    // 总共 i 个骰子朝上一面的点数之和为 j，
                    // 相当于当前骰子朝上一面的点数为 cur, 前面 i-1 个骰子的点数之和为 j-cur
                    dp[i][j] += dp[i-1][j-cur];
                }
            }
        }


        // 在 dp 中查找总共 n 个骰子朝上一面的点数之和为 j 的次数
        double[] res = new double[n*5+1];
        int index = 0;
        double all = Math.pow(6, n); // 总共有 6^n 种点数和
        for (int j = n; j <= n*6; j ++) {
            res[index ++] = dp[n][j]*1.0 / all;
        }

        return res;
    }
}

# 📚 References

🎁 公众号

各位小伙伴大家好呀，叫我小牛肉就行，目前在读东南大学硕士，上方扫码关注公众号「飞天小牛肉」，与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面

Last Updated: 2023/02/16, 11:27:10

← 合并区间剑指 Offer 10- I - 斐波那契数列→