problem:https://leetcode.com/problems/edit-distance/
二维爬台阶。dp[ i ][ j ] 代表长度为i的word1和长度为j的word2的最小转换次数。dp[ i ][ j ]可以由dp[ i ][ j - 1] 或 dp[ i - 1][j - 1]加一个数得到，也可以由dp[ i - 1][ j - 1] 加上替换一个数得到（如果最后两个数字相等，就不算替换）
class Solution { public: int minDistance(string word1, string word2) { int m = word1.size(); int n = word2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for(int i = 0;i <= m;i++) { dp[i][0] = i; } for(int j = 0;j <= n; j++) { dp[0][j] = j; } for(int i = 0;i < m; i++) { for(int j = 0;j < n;j++) { dp[i + 1][j + 1] = min(min(dp[i + 1][j], dp[i][j + 1]) + 1, dp[i][j] + (word1[i] == word2[j] ? 0 : 1)); } } return dp[m][n]; } };
[动态规划] leetcode 72 Edit Distance
原文：https://www.cnblogs.com/fish1996/p/11324106.html