[Acwing] 902. 最短编辑距离 线性DP

前言

哈哈哈哈哈,这也太简单了吧,DP？没想到啊,我竟然有一天可以看懂一道dp题 传送门 : https://www.acwing.com/problem/content/904/

思路

每一个dp 都可以从最后一步考虑 (我格局小,见识短)

既然从最后一步考虑

就相当于 你站在 搜索树的最后一个节点 考虑当前节点 有几个操作可以走就行了

于是分类一下

• 删除最后一个节点, f[i-1][j] +1
• 增加一个节点, f[i][j-1]+1
• 做变换操作, 要么早就相同了 要么没有 相同
  1. 如果相同的话呢 那么直接由f[i-1][j-1]变化过来即可
  2. 如果没相同,那么我们只需要再加上一个 1即可

这不就是 dfs 的思路吗？ 这也太顺了吧 hhhh

当然,还有最关键的一步 初始化: 从0-i 即 a长度为0 变到 i 需要 i步,即增加i个字符 否则 减少

CODE

#include 
#include 

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);

    for (int i = 0; i