解题思路：经典的动态规划问题，dp[i][j] 表示 s[0...i] 到 p[0...j] 的编辑距离。
数组初始化：s、p皆为空串，dp[0][0] = 0；s、p其中之一为空串时，只能做添加操作，因此dp[0][i] = i，dp[i][0] = i；
状态转移方程：分为 s[i] == p[j] 和 s[i] ！= p[j] 两种情况：
1.s[i] == p[j]，则添加这两个字符不影响编辑距离，即dp[i][j] = dp[i-1][j-1];
2.s[i] ！= p[j]，要使 s[0...i] == p[0...j] ，可以进行的操作有：
①添加/删除，对应dp[i-1][j]+1或dp[i][j-1]+1
②替换，对应dp[i-1][j-1]+1
class Solution {
public int minDistance(String str1, String str2) {
int len1 = str1.length();
int len2 = str2.length();
int[][] dp = new int[len1+1][len2+1];
dp[0][0] = 0;
for(int i=1; i<=len2; i++) dp[0][i] = i;
for(int i=1; i<=len1; i++) dp[i][0] = i;
for(int i=1; i<=len1; i++){
for(int j=1; j<=len2; j++){
if(str1.charAt(i-1)==str2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
else{
//str1.charAt(i-1)!=str2.charAt(j-1)
dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;
}
}
}
return dp[len1][len2];
}
}
