解题思路

这是一个编辑距离问题的变种。关键点：

  1. 动态规划定义：

    • 表示将 的前 个字符转换为 的前 个字符的最小代价
    • ：插入代价
    • ：删除代价
    • ：修改代价

  2. 状态转移：

    • 当 时：
    • 否则取以下三种操作的最小值：
      • 插入：
      • 删除：
      • 修改：

  3. 边界条件：

    • （全部删除）
    • （全部插入）

代码

class MinCost {
public:
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        
        // 初始化边界
        for(int i = 0; i <= n; i++) dp[i][0] = i * c1;
        for(int j = 0; j <= m; j++) dp[0][j] = j * c0;
        
        // 动态规划填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(A[i-1] == B[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = min(dp[i][j-1] + c0,  // 插入
                                 min(dp[i-1][j] + c1,  // 删除
                                     dp[i-1][j-1] + c2));  // 修改
                }
            }
        }
        
        return dp[n][m];
    }
};

import java.util.*;

public class MinCost {
    public int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
        // write code here
        int[][] dp = new int[n + 1][m + 1];
        
        // 初始化边界
        for(int i = 0; i <= n; i++) dp[i][0] = i * c1;
        for(int j = 0; j <= m; j++) dp[0][j] = j * c0;
        
        // 动态规划填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(A.charAt(i-1) == B.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i][j-1] + c0,  // 插入
                                      Math.min(dp[i-1][j] + c1,  // 删除
                                              dp[i-1][j-1] + c2));  // 修改
                }
            }
        }
        
        return dp[n][m];
    }
}

# -*- coding:utf-8 -*-
class MinCost:
    def findMinCost(self, A, n, B, m, c0, c1, c2):
        dp = [[0] * (m + 1) for _ in xrange(n + 1)]
        
        for i in xrange(n + 1): dp[i][0] = i * c1
        for j in xrange(m + 1): dp[0][j] = j * c0
        
        for i in xrange(1, n + 1):
            for j in xrange(1, m + 1):
                if A[i-1] == B[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i][j-1] + c0,
                                  dp[i-1][j] + c1,
                                  dp[i-1][j-1] + c2)
        
        return dp[n][m]

算法及复杂度

  • 算法：动态规划
  • 时间复杂度：，需要填充整个 表
  • 空间复杂度：，需要二维 数组