$\Huge\color{orchid}{点击此处获取更多干货}$

动态规划

最长上升子序列是单序列动态规划的典例，最长公共子序列则是双序列动态规划的典例。这次仍然会仔细分析状态表示和转移关系，并且给出最优子结构性质的说明，以后的帖子中就重点关注状态定义和转移关系，而不再细说最优子结构，重叠子问题了

由于涉及两个序列$s,t$，因此$dp$表也需要二维了，此处我们定义$dp(i,j)$为序列$s$的子段$s[0..i]$和序列$t$的子段$t[0..j]$中的最长公共子序列长度，这里提到的“子段”为原序列中一些连续的元素构成的序列。这里情况比较复杂，给出下面的图表来分析：

由此可以得出递推关系：
$$dp(i,j)=\begin{cases}dp(i-1,j-1)+1,s[i]=t[j] \\max\{dp(i-1,j),dp(i,j-1)\},s[i]\ne t[j]\end{cases}$$

最优子结构的说明比较长，借用一下别人的图：

为了方便计算，序列的下标可以从1开始。如果序列$s$长度为$m$，序列$t$长度为$n$，最终结果就是$dp(m,n)$

C++ 代码

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m, n;
    int** dp = new int*[m + 1];
    for (int i = 0; i <= n; i++) {
        dp[i] = new int[n + 1]();           //空括号代表默认赋值（0）
    }
    string str1, str2;
    cin >> str1 >> str2;
    str1 = ' ' + str1;                      //两字符串都向右偏移1，让有效下标从1开始
    str2 = ' ' + str2;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i] == str2[j]) {       //按照递推公式推
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}