c++动态规划 编辑距离
时间: 2023-12-13 10:33:44 浏览: 26
编辑距离问题是指给定两个字符串s1和s2,通过插入、删除、替换等操作,将s1转换为s2所需的最少操作次数。下面是C++实现编辑距离的动态规划代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int dp[N][N];
int main()
{
string s1, s2;
cin >> s1 >> s2;
int n = s1.size(), m = s2.size();
// 初始化边界条件
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
// 动态规划求解
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
cout << dp[n][m] << endl;
return 0;
}
```
其中,dp[i][j]表示将s1的前i个字符转换为s2的前j个字符所需的最少操作次数。边界条件为dp[i] = i和dp[j] = j,即将一个字符串转换为空串所需的最少操作次数为其长度。状态转移方程为:
- 当s1[i-1] == s2[j-1]时,dp[i][j] = dp[i-1][j-1],即不需要进行任何操作;
- 当s1[i-1] != s2[j-1]时,dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1,即需要进行插入、删除或替换操作。