[数据结构与算法]经典动态规划之编辑距离问题

题目描述

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

思路分析

此题是经典的动态规划题目，每年必考，因此，就不写暴力递归算法了，简单介绍一下递归思路，就直接上动态规划代码了，背也要背下来。
递归思路：
基本思路还是根据位置递归，比如，str1当前在i位置，str2当前在j位置，然后，递归返回的就是str1前i个位置转换成str2前j个位置的最小代价。
因此，递归出口就是str的i等于0时和str2的j等于0时，分别代码从空字符串转换成str2的代价和str1转换成空串的代价，分别就是str2的长度乘以插入和str1的长度乘以删除。
递归函数
观察题目的几种可能性：
1，插入
当str1的0到i位置等于str2的0到j-1位置，说明，str1就算加上i位置也不够，此时需要插入代价
2，删除
当str1的0到i-1位置等于str2的0到j位置时，说明当前str1的i位置多余，需要删除代价
3，替换
当str1的0到i-1位置等于str2的0到j-1位置时，说明前面对上了，此时，需要替换str1的i位置等于str2的j位置，需要替换代价
4，不需要代价
当str1的0到i-1位置等于str2的0到j-1位置时，说明前面对上了，此时，如果str1的i位置等于str2的j位置，则不需要操作
动态规划思路
有了前面的递归的思路，直接上动态规划思路：
先搞一张二维表，行是str1的i，列是str2的j，然后，先把第一行和第一列填上，然后，根据上面的递归关系填满动态规划表。

代码

    public static int f4(String str1,String str2,int ic,int dc,int rc){
        if(str1==null||str2==null){
            return 0;
        }
        char[] chars1=str1.toCharArray();
        char[] chars2=str2.toCharArray();
        int row=chars1.length+1;
        int col=chars2.length+1;
        int[][] dp=new int[row][col];
        for (int i = 1; i < row; i++) {
            dp[i][0]=dc+i;
        }
        for (int j = 1; j < col; j++) {
            dp[0][j]=ic+j;
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                //当i和j位置相等时，情况3和4谁先胜，谁先给dp[i][j]赋值
                if(chars1[i-1]==chars2[j-1]){
                    dp[i][j]=dp[i-1][j-1];
                }else {
                    dp[i][j]=dp[i-1][j-1]+rc;
                }
                //然后dp[i][j]依次和后面对比，找出最小的
                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[row-1][col-1];
    }