最小编辑代价 动态规划

dp[i][j]的值 代表str1[0...i-1] 编辑成str2[0...j-1]

边界条件 dp[0][0] = 0;

2 . 矩阵dp第一列即dp[0...i-1][0] 是把str1的字符全部删除为代价 dp[i][0] = dc*i

3. 矩阵dp第一行即dp[0][0...j-1] 代价是在空字符串插入str2[0...j-1] 所有字符 dp[0][j] = ic*j

str1 分三中情况得到str2 插入 删除 替换 从这个角度考虑写出 动态规划递归公式 感觉好简单为啥是较难题目

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
        char[]  arr1 =  str1.toCharArray();
        char[]  arr2 = str2.toCharArray();
        if(arr1.length == 0&&arr2.length==0){
            return 0 ; 
        }
        int row = arr1.length;
        int col = arr2.length;
        int[][] dp = new int[row+1][col+1];
        dp[0][0] = 0;
        for(int i = 1;i<row+1;i++){
            dp[i][0] = i*dc;
        }
        
        for(int j = 1;j<col+1;j++){
            dp[0][j] = j*ic;
        }
        for(int i = 1;i<row+1;i++){
            char c1 = arr1[i-1];
            for(int j= 1 ; j<col+1;j++){
                char c2 = arr2[j-1];
                if(c1 == c2){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = dp[i-1][j-1] +rc;
                }
//                 str1  删除
//                    dp[i][j] = dp[i-1][j] + dc;
//                 str1  添加
//                 dp[i][j] = dp[i][j-1]+ic;
                dp[i][j] = Math.min(dp[i][j],dp[i-1][j] + dc);
                dp[i][j] = Math.min(dp[i][j],dp[i][j-1]+ic);

                   
            }
        }
        
        return dp[row][col];
        
    }
}