[程序员代码面试指南]递归和动态规划-最小编辑代价(DP)

问题描述

输入 原字符串StrOrg，目标字符串StrTarget，插入、删除、替换的编辑代价ic,dc,rc。输出将原字符串编辑成目标字符串的最小代价。

解题思路

状态表示

dp[i][j]表示把strOrg[0:i]编辑成strTarget[0:j]的最小代价。

状态转移方程

从以下三种状态的取最小即可：

• 删除：dp[i][j]=dp[i-1][j]+dc。原串删除最后一个元素,再转移到目标串
• 插入：dp[i][j]=dp[i][j-1]+ic。原串变为目标元素删除最后一个元素，再插入最后一个元素。
• 替换：dp[i][j]=dp[i-1][j-1]+rc。由原串除最后一个元素变为目标串除最后一个元素，再替换最后一个元素（特别地，若两串最后一个元素相等，则省去rc）

对空间进行压缩，空间复杂度压缩至O(min(M,N))

使用一维数组，由于dp[i][j]既依赖于dp[i][j-1]又依赖于dp[i-1][j-1]，所以要有一个临时变量pre存dp[i-1][j-1].

注意

• 注意对第一行和第一列的初始化。
• 注意dp[i][j]表示的是不含strOri[i]和strTatget[j]元素的串，因为初始化第0行第0列的时候都表示的是空串。因此，开数组时也要多开一个位置。
• 为了空间复杂度是两串长度的较短值：设置长串和短串，保证列数为短串的长度+1，如果目标串比原串长，则在换一下ic和+dc操作的代价值。

代码1(空间复杂度O(N)版，其中N为目标串长度)

import java.util.Scanner;
public class Main {
    public static void main(String args[]) {
        Scanner in=new Scanner(System.in);
        while(in.hasNext()) {
            String strOri=in.next();
            String strTarget=in.next();
            int ic=in.nextInt();
            int dc=in.nextInt();
            int rc=in.nextInt();
            int editDis=getMinEditDis(strOri,strTarget,ic,dc,rc);
            System.out.println(editDis);
        }
    }
    
    public static int getMinEditDis(String strOri,String strTarget,int ic,int dc,int rc){
        int rows=strOri.length()+1;
        int cols=strTarget.length()+1;
        int dp[]=new int[cols];
        
        for(int j=0;j<cols;++j) {
            dp[j]=ic*j;//初始化第一行
        }
        
        for(int i=1;i<rows;++i) {
            int pre=dp[0];//pre记录dp[i-1][j-1]
            dp[0]=dc*i;//初始化第一列
            for(int j=1;j<cols;++j) {
                int ansTemp;
                if(strOri.charAt(i-1)==strTarget.charAt(j-1)) {//
                    ansTemp=pre;
                }
                else {
                    ansTemp=pre+rc;
                }
                int temp=dp[j];
                dp[j]=getMin(ansTemp,dp[j]+dc,dp[j-1]+ic);//状态转移
                pre=temp;//更新pre
            }
        }
        return dp[cols-1];
    }
    
    public static int getMin(int... vals) {
        int min=Integer.MAX_VALUE;
        for(int val:vals) {
            if(val<min) {
                min=val;
            }
        }
        return min;
    }
}

代码2(空间复杂度O(min(M,N))版)

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner in=new Scanner(System.in);
        while(in.hasNext()) {
            String strOri=in.next();
            String strTarget=in.next();
            int ic=in.nextInt();
            int dc=in.nextInt();
            int rc=in.nextInt();
            int editDis=getMinEditDis(strOri,strTarget,ic,dc,rc);
            System.out.println(editDis);
        }
    }
    
    public static int getMinEditDis(String strOri,String strTarget,int ic,int dc,int rc){
        String longs=strOri.length()>=strTarget.length()?strOri:strTarget;
        String shorts=strOri.length()<strTarget.length()?strOri:strTarget;
        int dp[]=new int[shorts.length()+1];
        
        if(strOri.length()<strOri.length()) {
            int temp=ic;
            ic=dc;
            dc=temp;
        }
        
        for(int j=0;j<shorts.length()+1;++j) {
            dp[j]=ic*j;//初始化第一行
        }
        
        for(int i=1;i<longs.length()+1;++i) {
            int pre=dp[0];//pre记录dp[i-1][j-1]
            dp[0]=dc*i;//初始化第一列
            for(int j=1;j<shorts.length()+1;++j) {
                int ansTemp;
                if(longs.charAt(i-1)==shorts.charAt(j-1)) {//
                    ansTemp=pre;
                }
                else {
                    ansTemp=pre+rc;
                }
                int temp=dp[j];
                dp[j]=getMin(ansTemp,dp[j]+dc,dp[j-1]+ic);//状态转移
                pre=temp;//更新pre
            }
        }
        return dp[shorts.length()];
    }
    
    public static int getMin(int... vals) {
        int min=Integer.MAX_VALUE;
        for(int val:vals) {
            if(val<min) {
                min=val;
            }
        }
        return min;
    }
}

[程序员代码面试指南]递归和动态规划-最小编辑代价(DP)

原文：https://www.cnblogs.com/coding-gaga/p/10852769.html