一、题目

1、原题链接

902. 最短编辑距离

2、题目描述

二、解题报告

1、思路分析

思路参考来源y总

1. dp[i][j]表示将a[1~i]变为b[1~j]中所有方案的操作次数最少的一个；
2. 按最后一步操作可以将状态分为：
   • 删除一个字符：dp[i-1][j]+1；
   • 增加一个字符：dp[i][j-1]+1；
   • 替换一个字符：dp[i-1][j-1]+1或两字符串完全相同不需要操作dp[i-1][j-1]。
3. 所以最终的状态转移方程为dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1,dp[i-1][j-1])

2、时间复杂度

时间复杂度为O(n²)

3、代码详解

#include <iostream>
#include <string>
using namespace std;
const int N = 1010;
string a, b;
int n, m;
int dp[N][N];
int main(){cin >> n >> a >> m >> b;//确保字符串下标从1开始，避免数组越界情况的考虑a = '1' + a;b = '1' + b;//删除i个字符for (int i = 0; i <= n; i++){dp[i][0] = i;}//增加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);if (a[i] == b[j]) {dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);}else {dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);}}}cout << dp[n][m];return 0;
}