动态规划 编辑距离

import java.util.*;


public class Solution {

    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i <= m; i++) {
            dp[i][0] = i*dc;
        }
        for(int j = 1; j <= n; j++) {
            dp[0][j] = j*ic;
        }
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                char c1 = str1.charAt(i-1);
                char c2 = str2.charAt(j-1);
                if(c1 == c2) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    int del = dp[i-1][j] + dc;
                    int add = dp[i][j-1] + ic;
                    int updt = dp[i-1][j-1] + rc;
                    dp[i][j] = Math.min(del, Math.min(add, updt));
                }
            }
        }
        return dp[m][n];
    }
}