• 状态表示：f[i]表示长度为i的最长上升子序列，末尾的最小数字。

• 状态计算：遍历a数组，在f数组中查找小于a[i]的最大的数，将a[i]插到这个数的后面一个位置。

• 最长上升子序列
• 最长上升子序列 II

最长公共子序列

给定两个长度分别为 $N$ 和 $M$ 的字符串 $A$ 和 $B$ ，求既是 $A$ 的子序列又是 $B$ 的子序列的字符串长度最长是多少。

例如： acbd 和 abedc 的最长公共子序列是 abd 长度为 $3$ 。

动态规划 $O(n^2)$

dp[i][j] 表示 $A$ 的前 $i$ 个字符和 $B$ 的前 $j$ 个字符中，最长公共子序列的长度。

状态转移：

• 如果 a[i] == b[j] ， dp[i][j] = dp[i-1][j-1] + 1 ，即把不包含这对字符的最长公共子序列加上这一对。
• 如果 a[i] != b[j] 则 dp[i][j] 由 dp[i-1][j] 或者 dp[i][j-1] 转移来，可以理解为这两个序列中一定有一个的最后一个字符不在最长公共子序列中，所以对分别去掉最后一个字符的状态取两者的最大值作为当前的状态。

for (int i=1;i<=n;i++)
{
    for (int j=1;j<=m;j++)
    {
        if (a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;
        else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    }
}

例题：

• 最长公共子序列

最短编辑距离

给定两个长度分别为 $n$ 和 $m$ 的字符串 $a$ 和 $b$，现在要将 $a$ 经过若干操作变为 $b$，可进行的操作有：

1. 删除 – 将字符串 $a$ 中的某个字符删除。
2. 插入 – 在字符串 $a$ 的某个位置插入某个字符。
3. 替换 – 将字符串 $a$ 中的某个字符替换为另一个字符。

现在请你求出，将 $a$ 变为 $b$ 至少需要进行多少次操作。

动态规划 $O(n^2)$

dp[i][j] 表示将 $a$ 的前 $i$ 个字符变成 $b$ 的前 $j$ 个字符所用的最少的操作数。

状态转移： 对三个操作进行分析：

1. 删除操作：把 $a[i]$ 删除之后 $a$ 的前 $i$ 个字符与 $b$ 的前 $j$ 个字符匹配，所以在这之前要满足 $a$ 的前 $i-1$ 个字符与 $b$ 的前 $j$ 个字符已经匹配，所以转移的是 dp[i-1][j] + 1。
2. 插入操作：添加一个字母之后 $a$ 的前 $i$ 个和 $b$ 的前 $j$ 个变得相同，说明没有添加前 $a$ 的前 $i$ 个已经和 $b$ 的前 $j-1$ 个已经相同，即 dp[i][j-1] + 1。
3. 替换操作：把 $a[i]$ 改成 $b[j]$ 之后 $a$ 的前 $i$ 个与 $b$ 的前 $j$ 个相同，所以之前 $a$ 的前 $i-1$ 个与 $b$ 的前 $j-1$ 个已经匹配，此时再判断 $a[i]$ 是否等于 $b[j]$ 即 dp[i-1][j-1] + (a[i] != b[j])。

所以 dp[i][j] 是从上面三个状态转移过来的，因为要求最短的操作数，所以上面三个值取最小值作为 dp[i][j] 的值。

初始化： dp[0][i] = i如果a初始长度就是0，那么只能用插入操作让它变成b dp[i][0] = i同样地，如果b的长度是0，那么a只能用删除操作让它变成b

for (int i=0;i<=n;i++) dp[i][0] = i;
for (int i=0;i<=m;i++) dp[0][i] = i;
 
for (int i=1;i<=n;i++)
{
    for (int j=1;j<=m;j++)
    {
        dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1);
        dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (a[i] != b[j]));
    }
}

例题：

• 最短编辑距离