知道是dp，没弄出状态方程。。
1 class Solution { 2 public: 3 int minDistance(string word1, string word2) { 4 // Start typing your C/C++ solution below 5 // DO NOT write int main() function 6 vector<vector<int>> f(word1.size()+1, vector<int>(word2.size()+1)); 7 for (int i = 0; i <= word1.size(); i++) f[i][0] = i; 8 for (int i = 0; i <= word2.size(); i++) f[0][i] = i; 9 for (int i = 1; i <= word1.size(); i++) { 10 for (int j = 1; j <= word2.size(); j++) { 11 if (word1[i-1] == word2[j-1]) f[i][j] = f[i-1][j-1]; 12 else f[i][j] = min(f[i][j-1], min(f[i-1][j], f[i-1][j-1]))+1; 13 } 14 } 15 return f[word1.size()][word2.size()]; 16 } 17 };
C#
1 public class Solution { 2 public int MinDistance(string word1, string word2) { 3 int[,] f = new int[word1.Length+1, word2.Length+1]; 4 for (int i = 0; i <= word1.Length; i++) f[i, 0] = i; 5 for (int i = 0; i <= word2.Length; i++) f[0, i] = i; 6 for (int i = 1; i <= word1.Length; i++) { 7 for (int j = 1; j <= word2.Length; j++) { 8 if (word1[i-1] == word2[j-1]) f[i, j] = f[i-1, j-1]; 9 else f[i, j] = Math.Min(f[i, j-1], Math.Min(f[i-1, j], f[i-1, j-1])) + 1; 10 } 11 } 12 return f[word1.Length, word2.Length]; 13 } 14 }