題意#
給定兩個字串。你可以對第一個字串進行三種操作：
- 新增一個字元
- 刪除一個字元
- 替換一個字元
你的任務是計算出：最少需要幾次操作，才能把第一個字串變成和第二個字串一模一樣？這也就是我們常說的「編輯距離」（Edit Distance 或 Levenshtein Distance）。
思路#
這是字串處理中經典的二維動態規劃題。
我們可以建立一個大小為 \( (n+1) \times (m+1) \) 的二維陣列 dp，其中 dp[i][j] 代表「將第一個字串的前 i 個字元，變成第二個字串的前 j 個字元，所需的最少操作次數」。
首先處理邊界條件：如果要把長度為 i 的字串變成空字串（也就是 j=0），只有一種可能：把裡面的字元全部刪掉，所以需要做 i 次刪除。同理，如果要從空字串變成對方的長度 j，那只能全加進去，需要 j 次新增。
接著，我們同時遍歷兩個字串：
- 當目前的兩個字元剛好相同時（
a[i-1] == b[j-1]），這一步根本不用操作，最少次數就會直接等於它們前面配對好的狀態，也就是dp[i-1][j-1]。 - 如果這兩個字元不同，我們就有三種選擇，且做完後操作次數要
+1，我們會挑最划算（次數最少）的一條路走：- 替換：直接把
a[i-1]換成b[j-1]，對應的狀態是dp[i-1][j-1] - 刪除：先把
a[i-1]刪掉，再處理其餘部分，對應的狀態是dp[i-1][j] - 新增：在第一個字串後面加一個
b[j-1]的字元，也就等於我們先把a變成b的前j-1個字元，對應狀態是dp[i][j-1]
- 替換：直接把
最後 dp[n][m] 即為解答。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
string a, b; cin >> a >> b;
int n = a.size(), m = b.size();
// dp[i][j] 表示 a 字串前 i 個字元變成 b 字串前 j 個字元所需的最少操作數
vector<vector<int>> dp(n+1, vector<int>(m+1));
// 邊界條件：如果其中一個是空字串，最少的步數就是把另一個字串全部新增或刪除
for (int i = 1; i <= n; i++) dp[i][0] = i;
for (int i = 1; i <= m; i++) dp[0][i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 如果當前比較的兩個字元相同，這步不用動，直接繼承前方的狀態
if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1];
// 否則，取「替換(dp[i-1][j-1])」、「刪除(dp[i-1][j])」、「新增(dp[i][j-1])」三者最小值再加 1 步操作
else dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) + 1;
}
}
cout << dp[n][m] << '\n';
}
