【ONE·基础算法 || 动态规划（三）】

总言

  主要内容：编程题举例，熟悉理解动态规划类题型（回文串问题、两个数组的 dp问题）。
  
  
  
  
  

7、回文串问题

7.1、 回文子串（medium）

  题源：链接。

7.1.1、题解

  1）、说明
  做法有很多，比如：
  中心扩展算法，时空复杂度分别为$O(n^2)、O(1)$。
  马拉车算法，时空复杂度分别为$O(n)、O(n)$。
  这里我们主要学习动态规划的思想，时空复杂度分别为$O(n^2)、O(n^2)$。虽然相对于其它两种解法而言，动态规划的方法不是最优解，但其能够将所有的子串是否是回文的信息，保存在dp表中。这在一些题中起到化繁为简的效果。

  
  
  
  2）、思路分析

  1、确定状态表示：
  如何将所有子串是否是回文的信息统计在dp表中？首先得找到所有的子串才行。从最直观的暴力解法来看，这需要我们使用两层循环，分别用于定位子串的起始字符 i 和结尾字符 j ，通过这样的遍历方式，我们能够捕捉到字符串中的每一个子串。
  我们获得这些子串的目的，是为了判断它们是否为回文子串。(i,j)位置帮助我们定位了某一个具体的子串，那么我们可以使用一个n×n的二维数组，这样dp[i][j]就用于记录这个 以 i 为起点、j 为终点的子串是否为回文子串。即：

dp[i][j]：用于表示s字符串中的(i,j)子串，是否是回文串。规定 i <= j.

  
  
  2、确定状态转移方程： 对于拿到的一个子串(i,j)，我们可以从区间两端分析起。

1、若 s[i] != s[j]，首尾两元素都不相等，说明这个子串不是回文串。此时有 dp[i][j] = false;
2、若 s[i] == s[j]，首尾两元素相等的时候，可以根据⻓度细分为三种情况。
   1）、i == j，长度为1，就一个元素构成子串。根据题目，这必然是回文串，此时有 dp[i][j] = true;
   2）、i + 1 == j，长度为2，就 i、j两个相邻元素构成子串。根据题目，这也是回文串，此时有 dp[i][j] = true;
   3）、子串长度大于2，已经确定s[i] == s[j]，此时要判断回文串，需要判断(i+1,j-1)是否构造回文串，也就是 dp[i][j] = dp[i+1][j-1]

  3、初始化： dp表中初始化是为了以防在填表时发生越界，但在本题中，dp表无需初始化，因为我们对 “ i == j 长度为 1 ” 和 “ i +1 == 长度为 2 ” 的情况做了细致处理，所以对于dp[i][j] = dp[i + 1][j - 1]。i+1 和 j-1向内收缩的时候，最后都会被归到上述两种情况中。

  4、填表顺序： 根据状态方程，填写(i,j)位置时，需要依赖(i+1,j-1)位置的元素，因此填表顺序应该是从下往上。每一行的左右填表顺序，无所谓。
  
  5、返回值： 题目要求统计并返回这个字符串中 回文子串 的数目，dp表中保存的是当前 (i,j) 子串是否是回文子串，因此我们需要返回dp表中true的个数。
  
  
  

  3）、题解
  

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        
        //1、创建dp表并初始化：无需特殊处理
        vector<vector<bool>> dp(n,vector<bool>(n));

        // 2、填表：从下往上
        int sum = 0;//统计返回值
        for(int i = n - 1; i >=0; --i)
        {
            for(int j = i; j < n; ++j)//注意这里枚举 j 时，j 的起始位置
            {
                if(s[i] == s[j])// 判断(i,j)两端
                    dp[i][j] = (i + 1 < j) ? dp[i+1][j-1] : true;//注意理解这种写法
                if(dp[i][j]) ++sum;
            }
        }
        // 3、返回
        return sum;
    }
};

7.2、 最长回文子串（medium）

  题源：链接。

7.2.1、中心扩散法

  「中心扩散法」的基本思想是：遍历每一个下标，以这个下标为中心，利用「回文串」中心对称的特点，往两边扩散，看最多能扩散多远。
  题解链接：字符串。
  
  
  
  

7.2.2、动态规划法

  1）、思路分析

  1、确定状态表示： 本题解题思路和7.1类似。我们定义一个dp表，dp[i][j] 中存储着(i,j)子串是否是回文串的信息。因为已知下标，自然，我们就可以根据下标，得到是回文串的那些子串的长度。len = j - i + 1.
  
  

  2、确定状态转移方程： 对于拿到的一个子串(i,j)，我们可以从区间两端分析起。

1、若 s[i] != s[j]，首尾两元素都不相等，说明这个子串不是回文串。此时有 dp[i][j] = false;
2、若 s[i] == s[j]，首尾两元素相等的时候，可以根据⻓度细分为三种情况。
   1）、i == j，长度为1，就一个元素构成子串。根据题目，这必然是回文串，此时有 dp[i][j] = true;
   2）、i + 1 == j，长度为2，就 i、j两个相邻元素构成子串。根据题目，这也是回文串，此时有 dp[i][j] = true;
   3）、子串长度大于2，已经确定s[i] == s[j]，此时要判断回文串，需要判断(i+1,j-1)是否构造回文串，也就是 dp[i][j] = dp[i+1][j-1]

  
  3、初始化： 无需初始化。

  4、填表顺序： 填表dp(i,j)时需要依赖(i+1,j-1)处的位置，因此需要从下往上填表。

  5、返回值： dp里面值为true的情况下，长度最大的子串的起始位置以及长度。
  
  
  
  2）、题解
  实际上，这里dp表相当于在做预处理工作：判断是否是回文串。
  嵌套了两层循环，时间复杂度为：$O(n^2)$。使用了一个二维数组dp，其大小为n x n，空间复杂度为：$O(n^2)$。

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();

        // 1、创建dp表并初始化
        vector<vector<bool>> dp(n, vector<bool>(n)); // dp[i][j]: (i,j)子串是否是回文串

        // 2、填表：从下往上
        int begin = 0;
        int maxlen = 0;
        for (int i = n - 1; i >= 0; --i) 
        {
            for (int j = i; j < n; ++j) 
            {
            
                if (s[i] == s[j])
                    dp[i][j] = (i + 1 < j) ? dp[i + 1][j - 1] : true;

                if (dp[i][j] &&(maxlen < j - i + 1)) //(i,j)是回文串，且出现了更大的长度
                    begin = i, maxlen = j - i + 1; // 更新起始位置和长度
            }
        }

        // 3、返回
        return s.substr(begin, maxlen);
    }
};

7.3、分割回文串 IV（hard）

  题源：链接。

7.3.1、题解

  1）、思路分析

  根据题目要求，我们需要将给定的字符串 s 分割成三个非空的回文子字符串。为了实现这一目标，可以采用以下策略：
  ①、选择一个分割点 (i, j)，其中 0 < i < j < n-1（n 是字符串 s 的长度），将字符串 s 分割成三个部分：[0,i-1]、[i,j]、[j+1,n-1]。
  ②、接下来，只需要判断这三个子字符串是否都是回文串即可。

  而判断某一段区间构成的子串是否是字符串，我们在先前两题中已经学过这个方法，可以使用动态规划来完成。相当于，这里的dp表其实是一个辅助工具/预处理过程。

  2）、题解
  嵌套了两层循环，两次，时间复杂度为：$O(n^2)$。使用了一个二维数组dp，其大小为 n x n，空间复杂度为：$O(n^2)$。

class Solution {
public:
    bool checkPartitioning(string s) {
        int n = s.size();

        // step1：获取一个dp表，表内存储着(i, j)子串是否是回文串的信息
        // 1、创建dp表并初始化
        vector<vector<bool>> dp(n,vector<bool>(n));

        // 2、填表：从下往上
        for(int i = n - 1; i >= 0; --i)
        {
            for(int j = i; j < n; ++j)
            {
                if(s[i] == s[j])
                    dp[i][j] = (i + 1 < j) ? dp[i+1][j-1] : true;
            }
        }

        // step2:根据获取的dp表，判断以(i, j)作为分割点的三个区间内的子串，是否均为回文串。
        for(int i = 1; i < n -1; ++i)// 因为题目给定了 length >=3, 这里为了省去边界判断，直接从  n-1> i >= 1、 n-1 > j >= i开始
        {                            // 也就是前后两端留了一个字符
            for(int j = i; j < n-1; ++j)
            {
                if(dp[0][i-1] && dp[i][j] && dp[j+1][n-1])
                    return true;
            }
        }
        return false;
    }
};

7.4、分割回文串II（hard）

  题源：链接。

7.4.1、题解

  1）、思路分析
  此题的整体思想和 单词拆分 类似。
  
  先来分析题目，要将字符串 s 经过切割后构成回文串，在极端情况下，如果字符串 s 本身不是回文串，那么长度为 n 的字符串 s 可能需要切割 n-1 次，才能将其分割成所有子串都是回文串（即每个字符单独成为一个回文串）。由此性质可知，对于任意有限长度的字符串 s，我们总是能将其切割形成回文串的。（理解这一点很重要，它有助于理解下述状态转移方程的推导）。

  1、确定状态表示： 要找到最少的分割次数，根据经验+题目要求，以 i 为结尾，则 dp[i] 表示以 0 为起点， i 为结尾的子串中，能构成回文串所需的最小切割次数。
  
  
  2、推导状态转移方程： 对 子串[0,i] 进行切割，可以分为以下两种情况：

1、[0,i] 整个子串本身就是回文串，无需进行任何切割，此时dp[i] = 0;
2、[0,i] 不构成回文串，需要进行切割。设 j 为切割点，有  0 < j <= i （注意，这里 j 不能为 0,因为0的情况上述已经判断了。j 可以为 i，也就是一个子串本身）
   由此，可将整个子串 [0, i] 分为两部分：[0, j-1] 和 [j, i]
   1）、先判断[j,i]是否构成回文串，若不构成，则当前切割点 j 不成立，需要重新寻找。
   2）、[j,i]构成回文串，此时只需要获取[0,j-1]子串中的最小切割次数，那么[0,i]子串中的切割次数，无非是在其后多切一刀。即；dp[i] = dp[j-1]+1.
   PS : 因为 j 切割点可选，而我们需要最小的切割次数，所以我们需要遍历所有可能的 j 值，并选择使 dp[i] 最小的那个。
        因此有 dp[i] = min( dp[i], dp[j-1]+1);

  优化：这里，为了快速获得某个区间(m,n)是否是回文串，可以借助之前几题的经验，先处理⼀个 dp 表，里面保存所有子串是否回⽂的信息。
  
  
  3、初始化： 一般，填表是为了防止不越界，在本题中，由于限制了 0 < j <= i，那么 dp[i] = dp[j-1]+1 是不会来到 j = 0处的。
  但由于我们后续进行了比较dp[i] = min( dp[i], dp[j-1]+1);，为了比较时， 取值为 0 的干扰，我们将dp表全都初始化为无穷大。

  4、填表顺序： 根据状态转移方程，从左到右填表。

  5、返回值： 根据我们的状态表示，这里需要返回dp[n-1]处的值。
  
  
  2）、题解
  时空复杂度：$O(n^2)$

class Solution {
public:
    int minCut(string s) {
        int n = s.size();

        // 0、准备工作：获取所有子串是否是回文串
        vector<vector<bool>> ispd(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; --i) 
        {
            for (int j = i; j < n; ++j) 
            {
                if (s[i] == s[j])
                    ispd[i][j] = (i + 1 < j) ? ispd[i + 1][j - 1] : true;
            }
        }

        // 1、创建dp表并初始化
        vector<int> dp(n, INT_MAX);
        // 2、填表
        for (int i = 0; i < n; ++i) {
            if (ispd[0][i]) dp[i] = 0; //[0,i] 整个子串本身就是回文串
            else 
            {
                for (int j = 1; j <= i; ++j) 
                {
                    if (ispd[j][i]) //[j,i]构成回文串
                        dp[i] = min(dp[j - 1] + 1, dp[i]);
                }
            }
        }
        // 3、返回
        return dp[n - 1];
    }
};

7.5、最长回文子序列（medium）

  题源：链接。

7.5.1、题解

  1）、思路分析
  需要注意理解这里的“子串”和“子序列”。

  
  1、确定状态表示： 尝试推导状态表示。
  按照惯例，一般会选择以 i 为结尾，dp[i]表示到达 i 位置时的最长回文子序列的长度。如果以这样的方式定义状态表示，在后续推导状态转移方程时，我们会发现无从下手，因为在只知道“长度”信息的情况下，无非判断一段序列是否是回文序列。
  
  关于此类单个字符串中，研究“回文子序列”，或者“回文子串”等问题， 我们的状态表示研究的对象一般都是选取原字符串中的一段区域[i，j]内部的情况。这里我们继续选取字符串中的一段区域来研究:

dp[i][j]表示: s字符串[i, j]区间内的所有的子序列中,最长的回文子序列的长度。规定 i <= j

  2、推导状态转移方程： 既然是在[i,j]区间段内挑选元素，看能否组成回文子序列，那么我们先从 i 、j 首尾两个元素看起。

1、s[i] == s[j]，首尾两个元素"相同"时：
   1）、若 i == j，即只有一个元素，此时dp[i][j] = 1。
   2）、若 i+1 == j，只有i、j两个相邻元素，此时dp[i][j] = 2。
   3）、若 i+1 < j ，那么[i，j]区间上的最长回文子序列，应该是 [i + 1，j - 1] 区间内的那个最长回文子序列，
       在其首尾添加上s[i]和s[j]，此时dp[i][j] = dp[i+1][j-1] + 2。

2、s[i] != s[j]，首尾两个元素"不相同"时：这表明i、j两个元素不能组成回文，就不能同时添加在一个回文串的左右。
   那么我们就应该让s[i]单独加在一个序列的左边，或者让s[j]单独放在一个序列的右边，看看这两种情况下的最大值:
   1）、单独加入s[i]后的区间在[i, j-1],此时最长的回文序列的长度就是dp[i][j-1];
   2）、单独加入s[j]|后的区间在[i + 1，j]，此时最长的回文序列的长度就是dp[i+ 1][j] ;
   取两者的最大值：dp[i][j] = max(dp[i][j - 1]，dp[i + 1][j])

  细节理解：当s[i] != s[j]时，我们不能直接跳到[i+1, j-1]，因为这样做会忽略掉可能以s[i]开头或以s[j]结尾的最长回文子序列。

  3、初始化： 因为对 i == j 和 i + 1 == j两种情况做了特殊处理，且dp表中要求 i <= j，因此不会发生越界行为。不用对dp表内数值做特殊处理。
  

  4、填表顺序： 根据状态转移方程，填写dp[i][j]时，需要依赖其左侧、下册、左下侧三个位置的dp值。因此填表顺序为：从下往上填表，每行从左往右填表。

  5、返回值： 根据状态表示，我们需要返回[0，n -1]区域上的最长回文序列的长度，即dp[0][n - 1]。

  
  
  2）、题解
  

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n= s.size();
        // 1、创建dp表并初始化
        vector<vector<int>> dp(n,vector<int>(n));// dp[i][j]：(i,j)子串中最长的回文子序列长度
        
        // 2、填表：从下往上、从左往右
        for(int i = n-1; i >= 0; --i)
        {
            dp[i][i] = 1;// i==j 时
            for(int j = i+1; j < n; ++j)// j 就可以从i+1开始
            {
                if(s[i] == s[j])
                    dp[i][j] = dp[i+1][j-1] + 2;// 这里的填表得到简化（不用三种情况分别写）
                else 
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
            }
        }

        // 3、返回
        return dp[0][n-1];
    }
};

7.6、让字符串成为回文串的最小插入次数（hard）

  题源：链接。

7.6.1、题解

  1）、思路分析

  1、确定状态表示： 根据经验+题目要求，回文串、回文序列通常会选择一段区间[i,j]来研究。因此状态方程为：

dp[i][j]：让以 i 为起点， j 为终点的子串成为回文串的最小插入次数。

  2、推导状态转移方程： 关于回文子序列和回文子串的分析方式，一般比较固定，先选择这段区域的左右端点的字符情况来分析。

1、s[i] == s[j]，首尾两个元素"相同"，插入次数看区间中间部分：
   1）、若 i == j，只有一个元素时，自成回文，无需插入。此时dp[i][j] = 0。
   2）、若 i+1 == j，只有i、j两个相邻元素，同样构成回文，无需插入。此时dp[i][j] = 0。
   3）、若 i+1 < j ，那么[i，j]区间上的最小插入次数，取决于 [i + 1，j - 1] 区间内的最小插入次数。即dp[i][j] = dp[i+1][j-1]。

2、s[i] != s[j]，首尾两个元素"不相同"时：这意味着i和j两个字符不能组成回文，需要在其中一边插入一个字符来使其变成回文。
   要么在区间右侧插入一个左端点值s[i]，要么在区间左侧插入一个右端点值s[j]。选择其中最小的插入次数:
   1）、在区间j的右侧插入一个s[i]，插入次数+1。此时左端点i和该数构成回文，最小插入次数需要看[i+1,j]区间，即dp[i][j] = dp[i + 1][j] + 1 ;
   2）、在区间i的左侧插入一个s[j]，插入次数+1。此时右端点j和该数构成回文，最小插入次数需要看[i,j-1]区间，即dp[i][j] = dp[i][j - 1] + 1;
   取两者的最小值：dp[i][j] = min(dp[i][j - 1]，dp[i + 1][j]) + 1

  
  
  3、初始化： 实则本题无需特别初始化。

  
  4、填表顺序： 根据状态转移方程，填写dp[i][j]时，需要依赖其左侧、下册、左下侧三个位置的dp值。因此填表顺序为：从下往上填表，每行从左往右填表。

  
  5、返回值： 根据状态表示，我们需要返回[0，n -1]区域上成为回文子串的最少插入次数，因此需要返回dp[0][n - 1]。

  
  
  2）、题解
  嵌套了两层循环，时间复杂度为：$O(n^2)$。使用了一个二维数组dp，其大小为n x n，空间复杂度为：$O(n^2)$。

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        // 1、创建dp表并初始化：本题无需特别初始化
        vector<vector<int>> dp(n,vector<int>(n));

        // 2、填表：从上往下（每行），从左往右（每列）
        for(int i = n-1; i >=0; --i)
        {
            dp[i][i] = 0;//其实也可以不用特意拎出来：单独一个字符，自成回文，无需切割
            for(int j = i+1; j < n; ++j)//因为上面处理的j = i的情况，这里 j 直接从 i+1开始
            {
                if(s[i] == s[j])
                    dp[i][j] = dp[i+1][j-1];// 这里i+1 == j的情况也包含在内：其依赖的位置本身就初始化为了0
                else
                    dp[i][j] = min(dp[i+1][j],dp[i][j-1])+1;//两种插入方式取最小
            }
        }
        // 3、返回
        return dp[0][n-1];
    }
};

8、两个数组的 dp

8.1、最长公共子序列（medium）

  题源：链接。

8.1.1、题解

  1）、思路分析
  此题为学习这类两个数组的dp的模板题，理解其中每步细节操作很重要。

  
  1、确定状态表示： 对于两个数组的动态规划，定义状态表的经验就是：
  1）、选取第一个数组中的[0，i]区间，以及第二个数组走的[0，j]区间作为研究对象；
  2）、结合题目要求，定义状态表示。
  
  根据本题题目，状态表示为：

dp[i][j]：以s1数组中的 [0,i] 区间，和s2数组中的 [0,j] 区间为结尾的"所有"子序列中，最长的公共子序列的长度。

  ※、强调： 这里状态表示研究的是[0,i]区间段内的所有子序列、[0,j]区间段内的所有子序列，并非单独的以i为结尾的子序列、以j为结尾的子序列。
  
  

  2、推导状态转移方程： 分析状态转移方程的经验就是根据 “最后一个位置” 的状况，分情况讨论。

  对于dp[i][j] ，可以根据s1[i]与s2[j]的字符分情况讨论:

  情况1）、s1[i] == s2[j]时： 这意味着s1[0,i] 和s2[0,j]区间内，最长公共序列的最后一个字符，一定会落在i、j下标的元素上。（以下是一个反证，可以略过）

  基于此，要求当前的最长公共子序列的长度，我们只需要在s1 的[0,i-1]区间和 s2 的 [0,j-1] 区间中找到一个最长的公共子序列，然后再加上当前匹配的字符 s1[i]（或 s2[j] ，因为它们是相等的）。
  所以，状态转移方程为：dp[i][j] = dp[i-1][j-1] + 1。
  
  
  情况2）、s1[i] != s2[j]时： 在这种情况下，最长公共子序列一定不会同时以s1[i]和s2[j]结尾。此时，要找最长公共子序列时，需要考虑下面三种情况：
  ①、在s1的[0，i-1]以及s2的[0，j]区间中寻找最长公共子序列：此时最大长度为dp[i-1][j];
  ②、在s1的[0，i]以及s2的[0，j-1]区间中寻找最长公共子序列：此时最大长度为dp[i][j- 1] ;
  ③、在s1的[0，i-1]以及s2的[0，j-1]区间中寻找最长公共子序列：此时最大长度为dp[i - 1][j - 1]。
  求三者中的最大值即可。

  细节说明： 仔细观察会发现，第三种包含在第一种和第二种情况里面。本题中求的是最大值，并不影响最终结果。如果题目换成求最长公共子序列的个数，则会重复计数，因此只需求前两种情况下的最大值即可。

  
  
  
  
  3、初始化：
  1）、关于字符串的dp问题，空串是有研究意义的，比如s1=""，无非表示子序列为空的情况。因此我们将原始dp 表的规模多加上一行和一列，表示空串。
  2）、引入空串的概念之后，会方便我们的初始化。但也要注意下标的映射关系，以及里面的填值要保证后续填表是正确的。
  ①、对下标映射：dp表中引入了虚拟节点表示空串，为了方便，可以在原子串s 中加入空g字符作为占位。如此一来，映射关系就得到了统一。即 s= " " + s1
  ②、填表：在本题中，虚拟节点行表示s1为空串，虚拟节点列表示s2为空串，无论哪一个，这种情况下，最长公共子序列的长度为 0，没有长度。因此第一行和第一列的值初始化为0，即可保证后续填表是正确的。

  4、填表顺序： 根据状态转移方程，从上往下填写每一行，从左往右填写每一列。

  
  5、返回值： 根据状态表示，返回dp[m][n]（注意这里的下标，因为引入了虚拟节点表示空串）。
  
  

  2）、题解
  在原表中添加" "空字符，使得下标映射与dp表中一致：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();

        // 1、创建dp表并初始化：这里引入了虚拟节点
        vector<vector<int>> dp(m + 1,vector<int>(n + 1,0));

        text1 = " " + text1;// 为了方便后续填表时下标对应
        text2 = " " + text2;

        // 2、填表：从上往下，从左到右
        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(text1[i] == text2[j])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }

        // 3、返回
        return dp[m][n];
    }
};

  若不这样写，那么需要注意原表的映射关系：

        // 2、填表：从上往下，从左到右
        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(text1[i-1] == text2[j-1])// 注意这里！
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }

8.2、不相交的线（medium）

  题源：链接。

8.2.1、题解

  1）、思路分析
  先来分析题目，题目要求绘制连线时，每条连线不会相交。这意味着，当我们为 nums1[i] 和 nums2[j] 绘制一条连线时，接下来的连线必须在这些元素之后（在各自数组中）寻找相同的元素。

  具体来说，如果我们已经为 nums1 中的某个元素 a 和 nums2 中的某个元素 b（且 a == b）绘制了一条连线，那么接下来的连线必须在 nums1 中 a 之后的元素和 nums2 中 b 之后的元素中寻找相同的元素。这一要求保证了连线的独立性，即它们不会相交。

  仔细观察会发现，这一逻辑实际上与寻找两个数组中的最长公共子序列（ LCS ）问题非常相似。在 LCS 问题中，我们需要在两个数组中找出按相同顺序出现的最长元素序列。这里的“按相同顺序出现”正对应了连线不相交的要求。 因此，我们可以将这个问题转化为在两个数组 nums1 和 nums2 中寻找最长公共子序列的问题。

  因为8.1中已经详细写过分析，此处不再赘叙。
  

  2）、题解
  

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();

        // 1、建表并初始化：引入虚拟节点
        vector<vector<int>> dp(m+1,vector<int>(n+1));

        // 2、填表：从左往右，从上往下。
        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(nums1[i-1] == nums2[j-1])// 注意下标映射关系
                    dp[i][j] = dp[i-1][j-1] +1;
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }

        // 3、返回
        return dp[m][n];
    }
};

8.3、 不同的子序列（hard）

  题源：链接。

8.3.1、题解

  1）、思路分析
  对于两个数组/字符串之间的dp问题，我们一般的思考方式如下：
  1）、选取第一个字符串的[0，i]区间以及第二个字符串的[0，j]区间当成研究对象，结合题目的要求来定义状态表示；
  2）、然后根据两个区间上 “最后一个位置的字符”，来进行“分类讨论”，从而确定“状态转移方程”。
  我们可以根据上面的策略，解决大部分关于两个字符串之间的dp问题。
  

  1、确定状态表示： 根据上述经验+本题的题目要求，我们选取 t 字符串中的区间 [0, i] 和 s 字符串中的区间 [0, j] 作为研究对象。定义二维数组 dp[i][j]，其中：
  dp[i][j] 表示：在 s 字符串的前 [0, j] 个字符所组成的所有子序列中，t 字符串的前 [0, i] 个字符出现的次数。

  
  
  2、推导状态转移方程： 要在 s[0, j] 字符串的所有子序列中，找字符串 t[0, i] （要求 t[0, i] 中的所有字符都被包含，且顺序一致）。我们可以根据 “在 s[0, j] 中满足要求的子序列是否包含 s[j]” 这一条件进行分情况讨论：

  1）、 s[0, j] 满足要求的子序列中包含 s[j] 元素： 这种情况只有当 t[i] == s[j] 时才成立。这时，我们可以在状态 dp[i-1][j-1] 中找到所有符合要求的子序列，然后在这些子序列的后面再加上一个字符 s[j]。因此，这种情况下的子序列数量为 dp[i-1][j-1]。（注意：在原序列中加上一个字符，原序列的数目是不变的）

  2）、s[0, j] 满足要求的子序列中不包含s[j]元素： 这时候，就需要去掉s[j]元素，在s[0, j-1]中，找t[0, i]。这意味着，这种情况下满足条件的子序列数量即 dp[i][j-1] 。

  两种情况加起来，dp[i][j] 的结果：dp[i][j] = dp[i-1][j-1]（有条件） + dp[i][j-1]
  
  其它：为什么不在 s[0,j]中找t[0,i-1]？不满足题意，题目是要求在s的子序列中找t，这说明给定t[0,i]，[0,i] 中出现的字符都要找全。（这点需要和之前的公共子序列区别开来）
  
  

  3、初始化： 引入虚拟节点初始化。需要注意两点：

  1）、虚拟节点中的需要保证后续填表时，状态转移方程正确。

  2）、下标映射关系：两种方法。①直接填表，但要注意s、t与dp的下标映射。②对s、t两个字符串分别头插一个占位字符" "，使得s、t、和dp间的下标映射对齐。

  
  4、填表顺序： 根据状态转移方程，从上往下填每一行，每一行左到右。
  
  5、返回值： 根据状态表示，需要返回dp[m][n]。
  
  

  2）、题解
  

class Solution {
public:
    int numDistinct(string s, string t) {
        // 注意这里谁是行，谁是列，注意与dp表统一
        int m = t.size();
        int n = s.size();

        // 1、创建dp表
        vector<vector<double>> dp(m+1,vector<double>(n+1,0));
        // 2、初始化：将第一行初始化为1
        for(int j = 0; j < n+1; ++j) dp[0][j] = 1;
        // 3、填表：从上往下，从左往右
        for(int i = 1; i < m+1; ++i)
        {
            for(int j = 1; j < n+1; ++j)
            {
                dp[i][j] += dp[i][j-1];
                if(s[j - 1] == t[i - 1])//注意原表和dp表中元素位置的映射关系
                    dp[i][j] += dp[i-1][j-1];
            }
        }
        // 4、返回
        return dp[m][n];
    }
};

8.4、通配符匹配（hard）

  题源：链接。

8.4.1、题解

  1）、思路分析
  对于两个数组/字符串之间的dp问题，一般的思考方式如下：
  1）、选取第一个字符串的[0，i]区间以及第二个字符串的[0，j]区间当成研究对象，结合题目的要求来定义状态表示；
  2）、然后根据两个区间上 “最后一个位置的字符”，来进行“分类讨论”，从而确定“状态转移方程”。
  我们可以根据上面的策略，解决大部分关于两个字符串之间的dp问题。
  

  1、确定状态表示： 根据上述，dp[i][j]表示，字符串p[0,j] 区间内的子串，能否完全匹配字符串s[0, 1]区间内的所有子串。
  
  

  2、推导状态转移方程： 要在p中找匹配s的字符，仍旧根据最后一个元素分情况讨论。根据题目，这里，p[j]可以有三类情况：
  
  1）、p[j] 为字母，这时候 p 要完全匹配 s ，则意味着 p[j] == s[i]。然后，我们需要看 p[j-1]区间内的子能否完全匹配上s[i-1]区间内的所有字符。即有：

	条件：p[j] = s[i] && dp[i-1][j-1] == true
	满足上述条件，则dp[i][j] = true，否则，dp[i][j] = false.

  
  2)、p[j] == '?'，根据题意，'?' 只能匹配一个字符，此时，就需要看p[j-1]区间内的子串能否完全匹配上 s[i-1]区间内的所有字符。

	条件：p[j] == '?' && dp[i-1][j-1] == true
	满足上述条件，则dp[i][j] = true，否则，dp[i][j] = false.

  3)、p[j] == '*'，根据题意，'*'能匹配任意多个字符。那么情况就有很多种：

'*'匹配0个字符时（空串），dp[i][j] 的状态，需要看 dp[i][j-1]

'*'匹配1个字符时，dp[i][j] 的状态，需要看 dp[i-1][j-1]
'*'匹配2个字符时，dp[i][j] 的状态，需要看 dp[i-2][j-1]
'*'匹配3个字符时，dp[i][j] 的状态，需要看 dp[i-3][j-1]
......
'*'匹配i个字符时，dp[i][j] 的状态，需要看 dp[0][j-1]

在上述这些情况中，只要有一种情况成立，那么dp[i][j] = true，即：
dp[i][j] = dp[i][j-1] || dp[i-1][j-1] || dp[i-2][j-1] || dp[i-3][j-1] || ......

  那么问题来了，枚举i、j位置，我们就需要两层for循环，这种情况又来一层小小的嵌套循环，三层循环下，时间复杂度会达到$O(n^3)$，有没有什么优化方法？（PS：解题时不优化，全情况或上，也是能通过的）
  
  以下举例优化理解：
  1、使用数学公式推导进行优化：

  可以发现，（2）式就是（1）式除第一项dp[i][j-1]以外的后面部分，代进去，即可得 $$dp[i][j]=dp[i][j-1]||dp[i-1][j]$$

  
  2、根据状态表示以及实际情况优化：

当p[j] = '*'时，
	1)、p[j]匹配空串，则dp[i][j]的情况需要看s[0,i]和p[j-1]，即dp[i][j-1]
	2)、p[j]匹配一个，但不舍去，此时dp[i][j]的情况需要看s[0,i-1]和p[j]，即dp[i-1][j]

  如果不能理解，可以多翻找一下官方解答中的评论区大佬们的补充解释。

  
  
  
  3、初始化： 为了处理边界情况，引入虚拟节点进行初始化。需要注意虚拟节点中的填值，以及下标映射关系。
  1）、首行初始化（dp[0][j]）：当输入字符串 s 为空时，字符模式 p 要能够匹配空字符串 s，则 p 必须仅由 '*' 字符组成（因为 '*' 可以匹配任意长度的字符序列，包括空序列）。因此，我们只用检查是否遇到了非 '*' 字符。如果遇到，则从该位置开始，dp[0][j] 为 false。
  2）、首列初始化（dp[i][0]）：当字符模式 p 为空时，除非输入字符串 s 也为空（即 dp[0][0] 的情况），否则 p 无法匹配任何非空字符串 s。因此，对于所有 i > 0，dp[i][0] 应初始化为 false。

  
  
  4、填表顺序：根据状态转移方程，从上往下填每一行，每行从左到右。
  
  
  5、返回值：根据状态表示，因为引入了虚拟节点，需要返回dp[m][n]处的值。
  
  
  
  2）、题解
  

class Solution {
public:
    bool isMatch(string s, string p) {
        // 这里注意行、列分别是谁，和dp表中行、列，以及状态方程对应上
        int m = s.size();
        int n = p.size();

        // 1、建表并初始化:
        vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
        
        s = " "+s;//引入虚拟节点，为方便映射关系，这里对原序列修改
        p = " "+p;

        dp[0][0] = true;
        for(int j = 1; j < n+1; ++j)//对首行初始化（首列除了[0][0]皆为false）
        {
            if(p[j] == '*') dp[0][j] = true;
            else break;//只要首次出现非'*'，后续全不能匹配
        }

        // 2、填表：从上往下，从左往右
        for(int i = 1; i < m+1; ++i)
        {
            for(int j = 1; j < n+1; ++j)
            {
                if(p[j] == '*')
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                else
                    dp[i][j] = (p[j] == '?' || p[j] == s[i]) && dp[i-1][j-1];//将两种情况归为统一来写
            }
        }

        // 3、返回
        return dp[m][n];
    }
};

8.5、正则表达式匹配（hard）

  题源：链接。

8.5.1、题解

  1）、思路分析
  对于两个数组/字符串之间的dp问题，一般的思考方式如下：
  1）、选取第一个字符串的[0，i]区间以及第二个字符串的[0，j]区间当成研究对象，结合题目的要求来定义状态表示；
  2）、然后根据两个区间上 “最后一个位置的字符”，来进行“分类讨论”，从而确定“状态转移方程”。
  我们可以根据上面的策略，解决大部分关于两个字符串之间的dp问题。
  

  1、确定状态表示： 根据上述经验+题目描述，这里，dp[i][j]表示，字符串p[0,j]区间内的子串能否完全匹配上字符串s[0,i]区间内的子串。
  

  2、推导状态转移方程： 判断p是否能匹配上s，以p的最后一个元素p[j]分情况讨论：
  1）、p[j]是a-z 的小写字母时，此时要使得 p 完全匹配上 s，则有s[i] == p[j]，最后一个位置的字符匹配。然后，我们再看s[0,i-1]和p[0,j-1]内的子串是否能完全匹配。既有：

	条件：p[j] = s[i] && dp[i-1][j-1] == true
	满足上述条件，则dp[i][j] = true，否则，dp[i][j] = false.

  
  2)、p[j] == '.'，根据题意，'.' 只能匹配任意单个字符，此时无论s[i]处是什么字母，均能匹配。那么我们只需看p[j-1]区间内的子串能否完全匹配上 s[i-1]区间内的所有字符即可。既有：

	条件：p[j] == '.' && dp[i-1][j-1] == true
	满足上述条件，则dp[i][j] = true，否则，dp[i][j] = false.

  
  3）、p[j] == '*'时，要看前一个字符p[j-1] 。题目保证每次出现字符 '*' 时，前面都匹配到有效的字符。即：

a、p[j-1] =='.'时，即p[j-1]、p[j]为'.*'，此时：
	'.*'可以是0个'.'，那么此时dp[i][j]需要看p[0,j-2]能否匹配上s[0,i]子串，即dp[i][j-2]
	'.*'可以是1个'.'，那么此时dp[i][j]需要看p[0,j-2]能否匹配上s[0,i-1]子串，即dp[i-1][j-2]
	'.*'可以是2个'.'，那么此时dp[i][j]需要看p[0,j-2]能否匹配上s[0,i-2]子串，即dp[i-2][j-2]
	'.*'可以是3个'.'，那么此时dp[i][j]需要看p[0,j-2]能否匹配上s[0,i-3]子串，即dp[i-3][j-2]
以此类推：只要满足其中一种情况即可，则有：dp[i][j] = dp[i][j-2]|| dp[i-1][j-2]||dp[i-2][j-2]||dp[i-3][j-2]||......

  同8.4题一样，若不进行优化处理，时间复杂度会非常高。优化处理的方式有二（见上题）：
  
  从数学公式推导的角度：
$$①dp[i][j]=dp[i][j-2]||dp[i-1][j-2]||dp[i-2][j-2]||dp[i-3][j-2]||......$$
  设 $i=i-1$，此时有：
$$②dp[i-1][j]=dp[i-1][j-2]||dp[i-2][j-2]||dp[i-3][j-2]||dp[i-4][j-2]||......$$
  将 ② 式代入 ① 式得：（匹配一个空串，或匹配一个，然后保留p[j-1]、p[j]）
$$dp[i][j]=dp[i][j-2]||dp[i-1][j]$$

b、p[j-1] == a~z字母时，同理。
	匹配空串，则需要看p[0,j-2]能否匹配上s[0,i]子串，即dp[i][j-2]
	匹配一个，然后保留。此时要看s[i] == p[j-1]，以及dp[i-1][j]

  
  
  综上，我们对状态转移方程进行整理：

1、当p[j]!= '*'，（ p[j]是'.'或a~z时）：
	dp[i][j] = (p[j] == '.' || p[j] == s[i]) && (dp[i-1][j-1] == true);
2、当p[j]== '*'时，
	dp[i][j] = dp[i][j-2] || ((p[j-1] == '*' || p[j-1] == s[i]) && dp[i-1][j] == true)

  
  
  3、初始化： 引入虚拟节点，防止填表时越界，需要注意两点。
  1）、下标映射关系。可以对原字符头插占位字符，使得下标映射一致。也可以什么都不做，在填表时注意隐射即可。
  2）、虚拟节点的初始化，要保证后续填表时状态转移方程正确。

  
  
  4、填表顺序： 根据状态转移方程，从上往下填每一行，每行中每个元素从左往右填表。
  
  
  5、返回值： 根据状态表示，因为引入了虚拟节点，需要返回dp[m][n]处的值。
  
  

  2）、题解
  

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();// 行
        int n = p.size();// 列，用于开辟dp表，注意这里行列与s、p两表对应关系，注意与dp表对应

        // 1、创建dp表:引入虚拟节点，(m+1)×(n+1)
        vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
        // 2、初始化
        s = " " + s;// 为了方便初始化和后续填表，统一下标映射关系
        p = " " + p;
        dp[0][0] = true;
        for(int j = 2; j < n+1; j+=2)// 初始化首行（s为空串时）
        {
            if(p[j] == '*') dp[0][j] = true;
            else break;//首次不满足，后续均不满足
        }

        // 3、填表：从上往下，从左到右
        for(int i = 1; i <=m; ++i)
        {
            for(int j = 1; j <=n; ++j)
            {
                if(p[j] == '*')
                    dp[i][j] = dp[i][j-2] || ((p[j-1] == '.' || p[j-1] == s[i]) && dp[i-1][j]);
                else 
                    dp[i][j] = (p[j] == '.' || p[j] == s[i]) && dp[i-1][j-1];
            }
        }

        // 4、返回
        return dp[m][n];
    }
};

8.6、 交错字符串（medium）

  题源：链接。

8.6.1、题解

  1）、思路分析
  分析此题，给定三个字符串 s1、s2 和 s3，我们需要验证 s3 是否可以由 s1 和 s2 交错组成。注意理解，这里“交错”指子串交错，其实根据示例1就能看出，并非指前一个元素来源自是s1 ，后一个元素就必须是 s2 。

  根据经验+题目要求，这里是否需要三个状态变量 i、j、k 分别表示 s1、s2、s3 中的一段区间呢？回答是不需要的，我们只需要两个状态变量 i 和 j，分别表示 s1 和 s2 中的待研究区间。那么 s3 的长度和组成，可以由 s1 和 s2 的长度及组合方式直接决定。

  引入虚拟节点：①根据题目示例3可知，空串在本题中是有研究意义的。②此外，s3的末尾下标位置需要依赖于s1和s2的状态变量。基于这两点，引入虚拟节点会方便很多。

  
  1、确定状态表示： dp[i][j]，表示s1[1,i]区间内的子串，以及s2[1,j]区间内的子串，交错拼接后是否能组成s3[1,i+j]区间内的子串。

  2、推导状态转移方程： 根据上述状态表示，要知道s3要构成交错字符串，则其每一个元素必须来源自s1或s2。因此，可以以s3的最后一个字符的来源，分情况讨论：
  1）、如果s1[i] == s3[i+j]，说明s3的最后一个字符来源于s1，此时只需要看 s1[1,i-1] 和 s2[1,j] ，是否能拼接成 s3[1, i+j-1]即可，若能拼接，则为true，否则，则为false。
  2）、如果s2[i] == s3[i+j]，说明s3的最后一个字符来源于s2，此时只需要看 s1[1,i] 和 s2[1,j-1] ，是否能拼接成 s3[1, i+j-1]即可，若能拼接，则为true，否则，则为false。
  3)、若s3的最后一个字符均不来源自s1、s2，此时无论如何拼接都是不成立的。

  综上：

dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j])
         || (s2[j] == s3[i + j] && dp[i][j - 1])

  只要满足其中一个即可。

  
  3、初始化： 引入了虚拟节点， 初始化时需要注意两点：
  ①下标隐射关系：在s1、s2、s3中头插了占位符进行解决。
  ②虚拟节点的初始化值要保证填表正确。

  
  4、填表顺序： 根据状态方程，从上往下填每一行，每一行从左往右。
  
  5、返回值： 根据状态表示，需要返回dp[m][n]处的值。
  

  2）、题解
  

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size();
        int n = s2.size();
        if(m + n != s3.size()) return false;// 注意这里长度要求
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;

        // 1、创建dp表并初始化
        vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));

        // 2、初始化
        dp[0][0] = true;
        for(int j = 1; j < n+1; ++j)// 首行：s1为空串，看s2与s3
        {
            if(s2[j] == s3[j]) dp[0][j] = true;
            else break;
        }
        for(int i = 1; i < m+1; ++i)// 首列：s2为空串，看s1与s3
        {
            if(s1[i] == s3[i]) dp[i][0] = true;
            else break;
        }

        // 3、填表
        for(int i = 1; i < m+1; ++i)
        {
            for(int j = 1; j < n+1; ++j)
            {
                if((s1[i] == s3[i+j] && dp[i-1][j])
                 || (s2[j] == s3[i+j] && dp[i][j-1]))
                dp[i][j] = true;
            }
        }

        // 4、返回
        return dp[m][n];
    }
};

  填表中，还可以简写为：

        // 3、填表
        for(int i = 1; i < m+1; ++i)
        {
            for(int j = 1; j < n+1; ++j)
            {
                dp[i][j] = (s1[i] == s3[i+j] && dp[i-1][j])
                 || (s2[j] == s3[i+j] && dp[i][j-1])
            }
        }

8.7、两个字符串的最小ASCII删除和（medium）

  题源：链接。

8.7.1、题解

  1）、思路分析
  分析题目，本题可以直接根据题目定义状态表示。当然，我们也可以使用正难则反的思想，将本题题意拆解为之前做过的套路，即找ASCII码值最大的公共子序列，如此一来，可以化用8.1中的思想。

  
  1、确定状态表示： 这里，我们使用正难则反的策略。根据经验+题目要求，dp[i][j]表示，在s1的[0,i]区间和s2的[0,j]区间，找公共子序列，使得ASCII码和最大。
  

  2、推导状态转移方程： 根据最后⼀个位置的元素分情况讨论：
  1）、当s1[i]==s2[j]时， 这意味着s1[0,i] 和s2[0,j]区间内，最大公共序列的最后一个字符，一定会落在i、j下标的元素上。我们只需要在s1 的[0,i-1]区间和 s2 的 [0,-1] 区间中，找到一个ASCII码最大的公共子序列，然后再加上当前 s1[i]的ASCII码即可（或 s2[j] ，因为它们是相等的）。

dp[i][j] = dp[i-1][j-1] + ASCII(s1[i])

  
  2）、当s1[i] != s2[j]时，：公共子序列的最大和会有三种可能：
  ①忽略s1[i]，在s1的[0,i-1]区间和s2的[0,j]区间中找公共子序列。即dp[i-1][j]。
  ②忽略s2[j]，在s1的[0,i]区间和s2的[0,j-1]区间中找公共子序列。即dp[i][j-1]。
  ③同时忽略s1[i]和s2[j]，在s1的[0,i-1]区间和s2的[0,j-1]区间中找公共子序列。即dp[i-1][j-1]。

//实际上，第三种情况，就包含在一二情况中。但这里求max，列出三者进行比较并不影响结果。
dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

  
  
  3、初始化： 这里，空串具有研究意义的，因此我们引入虚拟节点，将原始dp表的规模多加上一行、一列，表示空串。此时需要注意两点：
  ①原s1、s2和dp表的下标映射关系。
  ②虚拟行、列中的填值，要保证后续填表结果是正确的。

  
  4、填表顺序： 根据状态表示，从上往下填写每一行，从左往右填写每一列。

  
  5、返回值： 因为这里使用了“正难则反”的策略，我们不能直接返回dp表里面的某个值。需要进行处理：

1）、先找到dp[m][n]，也是最大公共ASCII 和;
2）、统计两个字符串的ASCII 码和sum;
3）、返回sum - 2*dp[m][n] 。

  
  
  2）、题解
  时空复杂度：$O(m\ast n)$

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size();
        int n = s2.size();
        // 1、创建dp表并初始化：注意这里行列关系，一一对应即可
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        // 2、填表：从左到右，从上到下
        for(int i = 1; i < m+1; ++i)
        {
            for(int j = 1; j <n+1; ++j)
            {
                if(s1[i-1] == s2[j-1])//注意下标映射
                    dp[i][j] = dp[i-1][j-1] + s1[i-1];
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
        // 3、返回
        int sum = 0;
        for(auto ch : s1) sum += ch;
        for(auto ch : s2) sum += ch;
        return sum - dp[m][n]*2;
    }
};

  其它写法：

        // 2、填表：从左到右，从上到下
        for(int i = 1; i < m+1; ++i)
        {
            for(int j = 1; j <n+1; ++j)
            {
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);// 这两种情况一定存在
                if(s1[i-1] == s2[j-1])//注意下标映射
                    dp[i][j] = max(dp[i-1][j-1] + s1[i-1], dp[i][j]);
            }
        }

8.8、 最长重复子数组（medium）

  题源：链接。

8.8.1、题解

  1）、思路分析
  可以发现，这题和8.1题很像，但区别在于，本题要找的是最长公共子数组（子数组和子序列的区别在之前已经提及过）。
  
  1、确定状态表示： 首先，我们需要明确，如果将状态定义为数组nums1的[0, i]区间和数组nums2的[0, j]区间内的最长公共子数组的长度，这并不符合我们的要求。因为公共子数组必须是连续的，所以在考虑到达i和j位置的最长公共子数组时，必须保证该子数组的前一个元素位于i-1和j-1的位置。

  因此，我们需要重新定义状态表示：

dp[i][j]：表示以nums1中第i个元素结尾，且以nums2中第j个元素结尾的最长公共子数组的长度。

  
  2、推导状态转移方程： 可以根据nums1[i]和nums2[j]是否相等来分情况讨论：
  1）、当nums1[i] == nums2[j]时：这意味着nums1[i]和nums2[j]可以加入到之前的最长公共子数组中，从而形成一个更长的公共子数组。因此，dp[i][j]的值应该是dp[i-1][j-1] + 1，即之前的最长公共子数组长度加1。
  2）、当nums1[i] != nums2[j]时：此时，nums1[i]和nums2[j]不能形成公共子数组的一部分。因此，dp[i][j]的值应该是0，表示在当前以i、j位置为结尾的子数组中，没有公共子数组。
  
  
  3、初始化： 为了防止越界，可以引入虚拟节点，添加一行和一列。需要注意两个问题：
  ①下标映射关系。
  ②虚拟节点填值。这里，首行dp[0][j]，表示nums1为空数组，首列dp[i][0]，表示nums2为空数组。当nums1或nums2其中一个数组为空时，最长公共子数组长度为0。
  
  
  4、填表顺序： 根据状态方程，从上往下填每一行，每一行左到右。

  5、返回值： 根据我们的状态表示，因该返回dp表中的最大值，它表示了nums1和nums2中公共的、长度最长的子数组的长度。
  
  

  2）、题解
  时空复杂度：$O(m\ast n)$

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();

        // 1、创建dp表并初始化
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));

        // 2、填表
        int ret = 0;
        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(nums1[i-1] == nums2[j-1])// 注意下标映射
                    dp[i][j] = dp[i-1][j-1] + 1;
                ret = max(dp[i][j],ret);
            }
        }

        // 3、返回
        return ret;
    }
};

Fin、共勉。