https://leetcode.com/problems/edit-distance/
1.动态规划，二维数组
class Solution {
public:int minDistance(string word1, string word2) {if(word1.empty() || word1.length()==0)return word2.length();if(word2.empty() || word2.length()==0)return word1.length();int row = word1.length();int col = word2.length();int a[row+1][col+1];int i, j, k;for(i=0;i<col+1;i++)//第一行a[0][i]=i;for(i=0;i<row+1;i++)//第一列a[i][0]=i;for(i=1;i<row+1;i++){for(j=1;j<col+1;j++){if(word1[i-1]==word2[j-1]){//这里需要注意字符的下标需要减1a[i][j]=a[i-1][j-1];}else{int tmp = min(a[i][j-1], a[i-1][j]);//插入、删除tmp = min(tmp, a[i-1][j-1]);//修改a[i][j]=1+tmp;//取3种方法的最小值，再加上1}}}return a[row][col];}
};2.动态规划，一维滚动数组
在更新a[i][j]时，只会用到左上角a[i-1][j-1]、左侧a[i][j-1]、上侧a[i-1][j] 这三个值，用二维数组明显浪费内存。
只要将a[i][j]左侧的所有值，以及上一行所有值保存到一个一位数组，不断滚动更新即可。
class Solution {
public:int minDistance(string word1, string word2) {if(word1.empty() || word1.length()==0)return word2.length();if(word2.empty() || word2.length()==0)return word1.length();int row = word1.length();int col = word2.length();int a[col+1];int i, j;for(i=0;i<col+1;i++)a[i]=i;for(i=1;i<row+1;i++){int left_up = a[0]; //记录原来二维数组中左上角 改 的值a[0]=i;//更新原来二维数组中左侧 插入 的值for(j=1;j<col+1;j++){int x = a[j];//记录原来二维数组上侧 删 的值if(word1[i-1]==word2[j-1]){a[j]=left_up;}else{int tmp = min(a[j-1], a[j]);tmp = min(tmp, left_up);a[j]=1+tmp;}left_up = x;//当前 删 的值，到下一个字符时已经变为左上角的 改 了}}return a[col];}
};