返回将str1编辑成str2的最小代价

问题描述：

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

【举例】
        str1="abc"，str2="adc"，ic=5，dc=3，rc=2 从"abc"编辑成"adc"，把'b'替换成'd'是代价最小的，所以返回2
        str1="abc"，str2="adc"，ic=5，dc=3，rc=100 从"abc"编辑成"adc"，先删除'b'，然后插入'd'是代价最小的，所以返回8
        str1="abc"，str2="abc"，ic=5，dc=3，rc=2 不用编辑了，本来就是一样的字符串，所以返回0。

思路

        动态规划的思想

        我们定义一个二维数组dp[N][M]，N表示str1的长度+1，M表示str2的长度+1，二维数组dp[i][j]含义是str1到第i位置的字符串转化为str2到第j位置的字符串的最小代价。

        二维数组dp[i][j]，dp[0][0] = 0,第一列的含义是str1转化为空的str2需要的最小代价即：dp[i][0] = dc * i。第一行的含义是空的str1转化为str2需要的最小代价即：dp[0][j] = ic * j 。

        按照str1转化为str2是否保存左后一个字符，分为两大类：

        1.保存str1最后一个字符，并且str2指针指向最后的位置。这一类根据str2中的最后一个字符是否的等于str1的最后字符又分为两小类。

                1.1 相等：str1[i - 1] == str2[j - 1] 复制。        dp[i][j] = dp[i - 1][j - 1]

                1.2 不相等：str1[i - 1] ！= str2[j - 1] 替换。        dp[i][j] =dp[i - 1][j - 1] + rc

        2.str1与str2的指针不同时指向最后的位置。

                2.1 str1的指正指向最后位置，str2的指针指向倒数第二的位置。即str1从0 - i-1 转化为str2的0 - j-2 ，str2[j-1]最后插入：dp[i][j] =dp[i][j - 1] + ic。

                2.2 str1的指正指向倒数第二的位置，str2的指针指向最后的位置。即str1从0 - i-2 转化为str2的0 - j-1 ，str1[i-1]最后删除：dp[i][j] =dp[i - 1][j] + dc。

        最后去这四种去请款的最小值存在dp[i][j]中。题目的最后结果存储在dp[N - 1][M - 1]中。

        同时我们也可以使用动态规划的空间压缩技术。

代码

        动态规划

    public static int minCost1(String s1, String s2, int ic, int dc, int rc) {
        if (s1 == null || s2 == null) {
            return 0;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int N = str1.length + 1;
        int M = str2.length + 1;
        int[][] dp = new int[N][M];
        for (int i = 1; i < N; i++) {
            dp[i][0] = dc * i;
        }
        for (int j = 1; j < M; j++) {
            dp[0][j] = ic * j;
        }
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + rc;
                }
                dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + ic);
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + dc);
            }
        }
        return dp[N - 1][M - 1];
    }

        动态规划的空间压缩技术

    public static int minCost2(String s1, String s2, int ic, int dc, int rc) {
        if (s1 == null || s2 == null) {
            return 0;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        char[] longs = str1.length >= str2.length ? str1 : str2;
        char[] shorts = str1.length < str2.length ? str1 : str2;
        if (str1.length < str2.length) {
            int tmp = ic;
            ic = dc;
            dc = tmp;
        }
        int[] dp = new int[shorts.length + 1];
        for (int i = 1; i <= shorts.length; i++) {
            dp[i] = ic * i;
        }
        for (int i = 1; i <= longs.length; i++) {
            int pre = dp[0];
            dp[0] = dc * i;
            for (int j = 1; j <= shorts.length; j++) {
                int tmp = dp[j];
                if (longs[i - 1] == shorts[j - 1]) {
                    dp[j] = pre;
                } else {
                    dp[j] = pre + rc;
                }
                dp[j] = Math.min(dp[j], dp[j - 1] + ic);
                dp[j] = Math.min(dp[j], tmp + dc);
                pre = tmp;
            }
        }
        return dp[shorts.length];
    }