题解 | #最小编辑代价#

我看大家都写的是迭代版本的，那我来写个递归版本的吧，思路一致，代码如下：
class Solution {
public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
// write code here
int[][] dp = new int[str1.length() + 1][str2.length() + 1];
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
dp[i][j]=-1;
}
}
int i=str1.length()-1;
int j=str2.length()-1;
int back = back(str1, str2, ic, dc, rc, i, j, dp);
return back;
}

public int back(String str1, String str2, int ic, int dc, int rc,int i,int j,int[][] dp){
    if (i==-1){
        return (j+1)*ic;
    }
    if (j==-1){
        return (i+1)*dc;
    }

   //备忘录：
    if (dp[i+1][j+1]!=-1){
        return dp[i+1][j+1];
    }

    int back;
    if (str1.charAt(i) == str2.charAt(j)) {
        back = back(str1, str2, ic, dc, rc, i - 1, j - 1, dp);
    } else {
        int a = back(str1, str2, ic, dc, rc, i - 1, j, dp) + dc;
        int b = back(str1, str2, ic, dc, rc, i, j - 1, dp) + ic;
        int c = back(str1, str2, ic, dc, rc, i - 1, j - 1, dp) + rc;
        back = getMin(a, b, c);
    }

   //存备忘录
    dp[i+1][j+1] = back;
    return back;
}


public int getMin(int a,int b,int c){
    return Math.min(Math.min(a,b),c);
}

}