題目
P2758 編輯距離
一道典型的線性 DP 題，
思路
狀態定義
像這種線性動態規劃，一種常見的狀態定義方法是：用 \(f_i\) 表示前 \(i\) 個元素滿足要求（只考慮前 \(i\) 個元素）時的最佳答案，
因此我們很自然地想到用 \(f(i,j)\) 表示將 \(A[1..i]\) 轉換為 \(B[1..j]\) 所需的最少操作次數，\(f(n,m)\) 就是問題的答案（\(n,m\) 分別表示字串 \(A,B\) 的長度），
狀態轉移
線性 DP 中，狀態轉移通常只需要考慮最后一點，
請設想這樣一種場景，\(A[1..i]\) 經過若干次操作被改成了 \(B[1..j]\)，且最后一步操作是在 \(A\) 的末尾進行的，我們不由地想到，這最后一步操作只可能是以下三種：
- 洗掉 \(A\) 末尾的字符；
- 在 \(A\) 的末尾插入一個字符；
- 修改 \(A\) 末尾的字符，
于是我們發現，有三種策略可以把 \(A[1..i]\) 修改為 \(B[1..j]\)：
- 先把 \(A[1..i-1]\) 變得跟 \(B[1..j]\) 一樣，再洗掉 \(A\) 末尾的字符；
- 先把 \(A[1..i]\) 變得跟 \(B[1..j-1]\) 一樣，再在 \(A\) 的末尾插入一個字符；
- 先把 \(A[1..i-1]\) 變得跟 \(B[1..j-1]\) 一樣，再修改 \(A\) 末尾的字符，
狀態轉移式：
\[f(i,j)=\min \left\{ \begin{aligned} f(i-1,j) & +1 \\ f(i,j-1) & +1 \\ f(i-1,j-1) & + \left\{ \begin{aligned} 0 & ,\textbf{if }A_i=B_j\\ 1 & ,\textbf{if }A_i \neq B_j \end{aligned} \right. \end{aligned} \right. \quad (i>0,j>0) \]邊界條件
觀察狀態轉移式，注意從左往右的下標變化，下標要么不變，要么變小，因此邊界就是下標為 \(0\) 的時候：
\[\begin{aligned} f(0,j) & = j \\ f(i,0) & = i \\ f(0,0) & = 0 \\ \end{aligned} \]遞推順序
由于從左往右下標要么不變，要么變小，因此遞推順序是從小到大列舉 \(i\) 和 \(j\)，
在開始遞推之前，應先求出所有邊界的值，
代碼
字串下標從 1 開始，
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2000 + 5;
char A[maxn];
char B[maxn];
int f[maxn][maxn];
int main()
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%s%s", A + 1, B + 1);
int n = strlen(A + 1);
int m = strlen(B + 1);
f[0][0] = 0;
for (int i = 1; i <= n; i++)
f[i][0] = i;
for (int j = 1; j <= m; j++)
f[0][j] = j;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
f[i][j] = min(f[i - 1][j] + 1, min(f[i][j - 1] + 1, f[i - 1][j - 1] + (A[i] == B[j] ? 0 : 1)));
printf("%d", f[n][m]);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/244166.html
標籤：其他
上一篇：找零錢-動態規劃
下一篇：【短道速滑六】古老的視頻去噪演算法（FLT_GradualNoise）決議并優化，可實作1920*1080 YUV資料400fps的處理能力。