动态规划 编辑距离

最小编辑代价

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];
    }
}
全部评论

相关推荐

头像
11-18 16:08
福州大学 Java
影流之主:干10年不被裁,我就能拿别人一年的钱了,日子有盼头了
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务