NC35 最小编辑代价

描述

给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。

示例1

输入：

"abc","adc",5,3,2

返回值：

2

示例2

输入：

"abc","adc",5,3,100

返回值：

8

备注：

$1 \leq |str_1|, |str_2| \leq 50001≤∣str1∣,∣str2∣≤5000$
$1 \leq ic, dc, rc \leq 100001≤ic,dc,rc≤10000$

import java.util.*;


public class Solution {
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here
        int n = str1.length();
        int m = str2.length();

        // 有一个字符串为空串
        if (n * m == 0) {
            return Math.max(n,m)*Math.min(dc,rc);
        }

        // DP 数组
        int[][] D = new int[n + 1][m + 1];

        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i*dc;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j*ic;
        }

        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = D[i - 1][j] + dc;
                int down = D[i][j - 1] + ic;
                int left_down = D[i - 1][j - 1];
                if (str1.charAt(i - 1) != str2.charAt(j - 1)) {
                    left_down += rc;
                }
                D[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return D[n][m];
    }
}