原题 dp 利用二维数组dp[i][j]存储状态： 从字符串A的0~i位子字符串 到 字符串B的0~j位子字符串，最少需要几步。（每一次删增改都算1步） 所以可得边界状态dp[i][0]=i，dp[0][j]=j。 以及状态转移方程 即当比较 word1[i] 和 word2[j] 字符 相等 时，所需步数与 word1[i-1] 和 word2[j-1] 相等。 状态转移方程为：dp[i][j]=dp[i-1][j-1] 否则，状态转移方程为dp[i][j]= min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1
class Solution { public: int minDistance(string word1, string word2) { int oneSize = word1.size() + 1; int twoSize = word2.size() + 1; int dp[oneSize][twoSize] = {0}; for (int i = 0; i < oneSize; i++) dp[i][0] = i; for (int j = 0; j < twoSize; j++) dp[0][j] = j; for (int i = 1; i < oneSize; i++) { for (int j = 1; j < twoSize; j++) { int temp; if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { temp = min(dp[i - 1][j], dp[i][j - 1]); dp[i][j] = min(dp[i - 1][j - 1], temp) + 1; } } } return dp[oneSize - 1][twoSize - 1]; } };转载于:https://www.cnblogs.com/ruoh3kou/p/9893420.html
相关资源：数据结构—成绩单生成器