解题思路:
此题是一道动态规划,想了很久,参考了很多代码,也是力扣第72题
注意事项:
i代表word1的字母数,j代表word2字母数。dp[i][j]代表最少需要的替换次数
参考代码:
#include #include #include using namespace std; int minn(int a, int b, int c) { a = min(a, b); a = min(a, c); return a; } int main() { string word1; string word2; cin >> word1 >> word2; int dp[202][202]; int m = word1.length(); int n = word2.length(); dp[0][0] = 0; for (int i = 1; i <= m; i++) { dp[i][0] = dp[i - 1][0] + 1; } for (int i = 1; i <= n; i++) dp[0][i] = dp[0][i - 1] + 1; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = minn(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1; } } cout << dp[m][n] << endl; return 0; }
0.0分
3 人评分
C语言程序设计教程(第三版)课后习题12.6 (C语言代码)浏览:794 |
2^k进制数 (C++代码)使用递归方法浏览:721 |
C语言训练-排序问题<1> (C++代码)浏览:600 |
C语言训练-计算1~N之间所有奇数之和 (C语言代码)浏览:653 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:1523 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:703 |
C语言训练-列出最简真分数序列* (C语言代码)浏览:619 |
用筛法求之N内的素数。 (C++代码)浏览:693 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:689 |
星期判断机 (C语言代码)浏览:859 |