【41. 最短编辑距离（线性DP）】

思路

1.状态表示 ：f[i][j]

• 集合：所有把a中的前i个字母 变成 b中前j个字母的集合的操作集合将a[1~i]变成b[1~j]的操作方式
• 属性：所有操作中操作次数最少的方案的操作数

2. 状态计算 ：从最后一步考虑

• 状态划分 以对a中的第i个字母操作不同划分
  • 有三种操作，所以有三个子集(增加、删除、更改)
• 考虑状态转移的时候
  • 先考虑如果我没有进行这个操作应该是什么状态
  • 然后考虑你进行这一步操作之后会对你下一个状态造成什么影响
  • 然后再加上之前状态表示中你决策出来的那个DP属性，这样就可以自然而然地搞出来转移方程啦

3. 三种划分

• 在该字母之后添加
  • 添加一个字母之后变得相同，说明没有添加前a的前i个已经和b的前j-1个已经相同
  • 即 ： f[i][j] = f[i][j-1] + 1
• 删除该字母
  • 删除该字母之后变得相同，说明没有删除前a中前i-1已经和b的前j个已经相同
  • 即 ： fi][j] = f[i-1][j] + 1
• 替换该字母
  • 替换说明对应结尾字母不同，则看倒数第二个
  • 即： fi][j] = f[i-1][j-1] + 1
• 啥也不做
  • 对应结尾字母相同，直接比较倒数第二个
  • 即： f[i][j] = f[i-1][j-1]

4. 细节问题：初始化

• 先考虑有哪些初始化嘛
  1. 你看看在for遍历的时候需要用到的但是你事先没有的
     （往往就是什么0啊1啊之类的）就要预处理
  2. 如果要找min的话别忘了INF
     要找有负数的max的话别忘了-INF

1.f[0][i]如果a初始长度就是0，那么只能用插入操作让它变成b
  f[i][0]同样地，如果b的长度是0，那么a只能用删除操作让它变成b
2.f[i][j] = INF //虽说这里没有用到，但是把考虑到的边界都写上还是保险
1
2
3

题目

代码

#include 
#include 
using namespace std;

const int N = 1010;
char a[N], b[N];
int f[N][N];
int n, m;

int main()
{
    cin >> n >> (a + 1);
    cin >> m >> (b + 1);
    for (int i = 0; i <= m; i ++) f[0][i] = i;   //字符串a长度为0，则需要将a进行i次增加操作，才能变成b 
    for (int i = 0; i <= n; i ++) f[i][0] = i;   //字符串b长度为0，则需要将a进行i次删除操作，才能变成b
    
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m ; j ++)
            {
                f[i][j] = min(f[i - 1][j] + 1,f[i][j - 1] + 1);
                if (a[i] == b[j])  f[i][j] = min(f[i][j], f[i - 1][j - 1]);
                else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
            }
    
    cout << f[n][m];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

总结

• 背包问题分类方式：第i个物品选几个，按照不同的选法进行分类
• 最长公共子序列：看最后俩个字母的情况进行分类
• 最长上升子序列：看倒数第二个数选哪个进行分类
• 数字三角形：枚举最后一步怎么走下来进行分类

综上：分类方式一般考虑最后一步