动态规划 编辑距离
最小编辑代价
http://www.nowcoder.com/questionTerminal/05fed41805ae4394ab6607d0d745c8e4
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]; } }