字符串-将str1编辑成str2所需最小代价(hard)

一、题目描述

二、解题思路

该题目使用动态规划的思想来解决问题

刚开始我还在想，删除+添加的操作可以等价为替换操作，如果替换操作的Cost大于删除+添加组合操作的Cost之和就需要把 rc=dc+ic。

但是在动态规划中，如果对三种不同的操作方式进行比较然后取较小值，不用进行上面的替换操作就可以达到效果，假设i表示指向str2的指针，j表示指向str1的指针，将str1->str2的过程中：

无非就是一个从对角线 [i-1][j-1] ->(替换) [i][j] cost=rc

另一个从 [i-1][j-1] ->(删除) [i-1][j] ->(添加) [i][j] cost=dc+ic

所以这里的状态转移方程就是：

deleteCost = dp[i][j-1]+dc;

addCost = dp[i-1][j]+ic;

replaceCost = dp[i-1][j-1]+rc;

dp[i][j] = Min(deleteCost,addCost,replaceCost)

初始化dp数组：

dp[0][j] = j*dc ：代表str2为空串，str1只能删除，则花费为 j × dc

dp[i][0] = i*ic ：代表str1为空串，str1只能添加，则花费为 i × ic

三、代码实现

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) {

        //使用动态规划找两个字符串的最小代价
        int[][] maxCostArr=new int[str2.length()+1][str1.length()+1];

        //dp数组进行初始化
        //初始化第一行，当str2为空字符串时
        for(int i=0;i<=str1.length();i++){
            maxCostArr[0][i]=i*dc;
        }
        //初始化第一列，当str1为空字符串时
        for(int i=0;i<=str2.length();i++){
            maxCostArr[i][0]=i*ic;
        }

        //双层循环对dp数组进行修改
        for(int p2=1;p2<=str2.length();p2++){
            for(int p1=1;p1<=str1.length();p1++){
                if(str2.charAt(p2-1)==str1.charAt(p1-1)){
                    //Cost不需要增加
                    maxCostArr[p2][p1]=maxCostArr[p2-1][p1-1];
                }else{
                    //计算三种情况下的代价值，去最小值
                    int deleteCost=maxCostArr[p2][p1-1]+dc;
                    int addCost=maxCostArr[p2-1][p1]+ic;
                    int replaceCost=maxCostArr[p2-1][p1-1]+rc;
                    maxCostArr[p2][p1]=Math.min(deleteCost,Math.min(addCost,replaceCost));
                }
            }
        }
        return maxCostArr[str2.length()][str1.length()];
    }
}