LeetCode 583. 两个字符串的删除操作（动态规划）

示例：
输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
 
提示：
给定单词的长度不超过500。
给定单词中的字符只含有小写字母。

class Solution {
public:
    int minDistance(string word1, string word2) {
    	int n1 = word1.size(), n2 = word2.size(), i, j;
    	if(n1==0 || n2==0)
    		return max(n1,n2);
    	vector<vector<int>> dp(n1+1,vector<int>(n2+1,INT_MAX));
    	for(i = 0; i <= n1; ++i)
    		dp[i][0] = i;//第二字符串长度为0，需要删除第一个字符串多少个字符
    	for(i = 0; i <= n2; ++i)
    		dp[0][i] = i;
    	for(i = 1; i <= n1; ++i)
    	{
    		for(j = 1; j <= n2; ++j)
    		{
    			if(word1[i-1]==word2[j-1])//w1第i个字符和 w2第j个字符相等
    				dp[i][j] = dp[i-1][j-1];//需要删除的最少字符等于前面的
    			else
    			{
    				dp[i][j] = 1+min(dp[i][j-1],dp[i-1][j]);
    				//不相等
    				//可以有两种方式，删除一个 j，然后次数+1，dp[i][j-1]+1
    				//或者删除一个 i，次数+1，dp[i-1][j]+1
    				//其实还有一个删除i,j，次数+2，dp[i-1][j-1]+2，不可能次数最少
    			}
    		}
    	}
    	return dp[n1][n2];
    }
};