多维线性DP

绝地灬酷狼 2024-04-03 11:09 53阅读 0赞

## 多维线性DP ##

##### [72. 编辑距离][72.] #####

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

*  插入一个字符
 *  删除一个字符
 *  替换一个字符

示例 1：

> 输入：word1 = “horse”, word2 = “ros”  
> 输出：3  
> 解释：  
> horse -> rorse (将 ‘h’ 替换为 ‘r’)  
> rorse -> rose (删除 ‘r’)  
> rose -> ros (删除 ‘e’)

示例 2：

> 输入：word1 = “intention”, word2 = “execution”  
> 输出：5  
> 解释：  
> intention -> inention (删除 ‘t’)  
> inention -> enention (将 ‘i’ 替换为 ‘e’)  
> enention -> exention (将 ‘n’ 替换为 ‘x’)  
> exention -> exection (将 ‘n’ 替换为 ‘c’)  
> exection -> execution (插入 ‘u’)

**提示：**

*  `0 <= word1.length, word2.length <= 500`
 *  `word1` 和 `word2` 由小写英文字母组成

这里可以把  d p \[ i \] \[ j \] dp\[i\]\[j\] dp\[i\]\[j\]定义为 w o r d 1 word1 word1的前 i i i个字符到 w o r d 2 word2 word2的前 j j j个字符的最少操作数

d p \[ i − 1 \] \[ j \] dp\[i - 1\]\[j\] dp\[i−1\]\[j\]看作是`插入一个字符`,然后 w o r d 1 word1 word1在第 i i i个位置上插入一个 w o r d 2. c h a r A t ( j ) word2.charAt(j) word2.charAt(j)字符

d p \[ i \] \[ j − 1 \] dp\[i\]\[j - 1\] dp\[i\]\[j−1\]看作是`删除一个字符`然后 w o r d 2 word2 word2在第 j j j个位置上删除一个 w o r d 2. c h a r A t ( j ) word2.charAt(j) word2.charAt(j)字符

d p \[ i − 1 \] \[ j − 1 \] dp\[i - 1\]\[j - 1\] dp\[i−1\]\[j−1\]看作是`替换一个字符`然后 w o r d 1 word1 word1在第 i i i个位置的字符 w o r d 1. c h a r A t ( i ) word1.charAt(i) word1.charAt(i)替换成字符 w o r d 2. c h a r A t ( j ) word2.charAt(j) word2.charAt(j)

那么状态转移方程为：

$ dp\[i\]\[j\] = Math.min(dp\[i\]\[j - 1\] + 1, Math.min(dp\[i - 1\]\[j\] + 1, dp\[i - 1\]\[j - 1\] + ( word1.charAt(i - 1) != word2.charAt(j - 1) ? 1 : 0)))$

然后考虑一下初始化操作：

当 w o r d 2 word2 word2的长度为 0 0 0的时候, d p \[ i \] \[ 0 \] dp\[i\]\[0\] dp\[i\]\[0\]为第 i − 1 i-1 i−1位的操作数加 1 1 1

当 w o r d 1 word1 word1的长度为 0 0 0的时候, d p \[ 0 \] \[ j \] dp\[0\]\[j\] dp\[0\]\[j\]为第 j − 1 j-1 j−1位的操作数加 1 1 1

for (int i = 1; i <= n; i++) {
        
      dp[i][0] = dp[i - 1][0] + 1;
    }
    for (int j = 1; j <= m; j++) {
        
      dp[0][j] = dp[0][j - 1] + 1;
    }

最后完整化代码：

class Solution {
        public int minDistance(String word1, String word2) {
            int n = word1.length();
          	int m = word2.length();
          	int[][] dp = new int[n + 1][m + 1];
          	for (int i = 1; i <= n; i++) {
              dp[i][0] = dp[i - 1][0] + 1;
            }
            for (int j = 1; j <= m; j++) {
              dp[0][j] = dp[0][j - 1] + 1;
            }
            for (int i = 1; i <= n; i++) {
              for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.min(dp[i][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i - 1][j - 1] + ( word1.charAt(i - 1) != word2.charAt(j - 1) ? 1 : 0)));
              }
            }
          	return dp[n][m];
        }
    }

这个题做懂之后，建议做一下

[P1279 字串距离][P1279]

[72.]: https://leetcode.cn/problems/edit-distance/
[P1279]: https://www.luogu.com.cn/problem/P1279