- #include <bits/stdc++.h>
- using namespace std;
- string str1, str2;
- vector <vector<int>> dp;
- vector <vector<bool>> visited;
- int re (int i, int j) {
- if (i < 0 and j < 0) {
- return 0;
- } else if (i < 0) {
- return j + 1;
- } else if (j < 0) {
- return i + 1;
- } /*else if (visited[i][j] == 1) {
- return dp[i][j];
- } */
- if (str1[i] == str2[j]) {
- visited[i][j] = 1;
- return re(i - 1, j - 1);
- } else {
- int a, b, c;
- a = re(i, j - 1) + 1;
- b = re(i - 1, j) + 1;
- c = re(i - 1, j - 1) + 1;
- visited[i][j] = 1;
- return min(a, min(b, c));
- }
- }
- int main()
- {
- cin >> str1 >> str2;
- dp.resize(str1.length());
- visited.resize(str1.length());
- for (int i = 0; i < str1.length(); i++) {
- dp[i].resize(str2.length());
- visited[i].resize(str2.length());
- }
- cout << re(str1.length() - 1, str2.length() - 1);
- return 0;
- }
複製代碼 |