【每日算法Day 34】动态规划基础2🚩
Wallace Xu 2020-07-04 动态规划
今天的题目都是使用二维空间的动态规划题目，个人感觉许多和字符串相关的问题动态规划的特性比较隐蔽，更是不容易看出来。
# LeetCode 72. 编辑距离 (opens new window)
# 题目描述
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
# 示例
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
1
2
3
4
5
6
2
3
4
5
6
# 解题思路
比较两个字符串的最后一位，假设为word1的第i位和word2的第j位：
word1:[0]...[][][i]
word2:[0]...[][j]
1
2
2
- 如果两者相同，则可以忽略他们继续比较前面的word1[0,i-1]和word2[0,j-1]，即不需要进行上面的三种操作之一。
- 如果两者不同，则需要进行上面的操作了（操作数+1）。可以选择在word1后
插入和word2[j]相同的字符，这样问题就变成了比较word1[0,i]和word2[0,j-1]；可以选择删除word1[i]，这样问题就变成了比较word1[0,i-1]和word2[0,j]；可以选择将word1[i]替换为和word2[j]相同的字符，这样问题就变成了比较word1[0,i-1]和word2[0,j-1]。在这三种操作的结果中选择最小值+1就是当前字符串的最短编辑距离。 - 当比较到出现空串时（或一开始就有空串），那么另一个字符串的当前长度就是编辑距离。
很明显这就变成了子问题，可以使用递归自顶向下求解：
public int minDistance(String word1, String word2) {
//防止有空串，递归的出口
if (word1==null&&word2==null) return 0;
if (word1==null||word1.length()==0) return word2.length();
if (word2==null||word2.length()==0) return word1.length();
int n=word1.length(),m=word2.length();
if (word1.charAt(n - 1) == word2.charAt(m - 1)) {
return minDistance(word1.substring(0, n - 1), word2.substring(0, m - 1));
} else {
return 1+Math.min(minDistance(word1.substring(0, n), word2.substring(0, m - 1)),
Math.min(minDistance(word1.substring(0, n-1), word2.substring(0, m - 1)),
minDistance(word1.substring(0, n-1), word2.substring(0, m )))
);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
不过这样会有大量重复的计算，时间效率非常低，可以使用动态规划的思想进行优化。从上面的逻辑中抽象出状态转移方程。
minDistance(word1[0,i],word2[0,j]) = minDistance(word1[0,i-1],word2[0,j-1])，if word1[i]==word2[j]
= 1+min(minDistance(word1[0,i-1],word2[0,j-1]),minDistance(word1[0,i],word2[0,j-1]),minDistance(word1[0,i-1],word2[0,j]))，if word1[i]!=word2[j]
1
2
2
由于word1和word2是两个独立的状态，所以一定是二维状态数组，使用dp[i][j]表示minDistance(word1[0,i],word2[0,j])。初始化时，dp[0][j]=j，dp[i][0]=i，表示空串和两个字符串对应位置子串的编辑距离。由于java中字符串取字符从0开始，第一个字符是第0位，而dp数组的第0行和第0列已经用于表示空串的编辑距离，dp从第1行第1列开始，所以dp数组长宽要比两个字符串的长度各大1。
public int minDistance(String word1, String word2) {
if (word1==null&&word2==null) return 0;
if (word1==null||word1.length()==0) return word2.length();
if (word2==null||word2.length()==0) return word1.length();
int n=word1.length(),m=word2.length();
//dp[i][j]表示word1的[0,i]的子串到word2的[0,j]的子串的最小编辑距离
int[][] dp=new int[n+1][m+1];
//边界状态初始化
for (int i = 0; i < n+1; i++) {
dp[i][0]=i;
}
for (int j = 0; j < m + 1; j++) {
dp[0][j]=j;
}
//按照状态转移方程编写dp过程
for (int i = 1; i < n+1 ; i++) {
for (int j = 1; j < m+1 ; j++) {
if (word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j]=dp[i-1][j-1];
else
dp[i][j]=1+Math.min(dp[i-1][j-1],Math.min(dp[i][j-1],dp[i-1][j]));
}
}
return dp[n][m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# LeetCode 97. 交错字符串 (opens new window)
# 题目描述
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
# 示例
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
1
2
3
4
5
2
3
4
5
# 解题思路
一开始看到这题没看出动态规划解法，尝试了双指针交替扫描的方法，不过事实证明（许多用例下）是错的行且没法调整。
//错误的解法，在输入的字符串分别为"aa"、"ab"、"aaba"就会错误
//这是由于该算法首先匹配完s1和s3的前两个字符aa，发现s2和s3剩余的字符不匹配
//事实上应该是s1先匹配1个a，再由s2匹配ab，最后s1再匹配一个a
//按照这个思路，似乎让程序自动选择每次匹配的字符个数是不太现实的
public static boolean isInterleave(String s1, String s2, String s3) {
if (s1.length()+s2.length()!=s3.length()) return false;
int p1=0,p2=0,p3=0;
while (p3 < s3.length()) {
while (p1 < s1.length() && p3 < s3.length() && s1.charAt(p1) == s3.charAt(p3)) {
p1++;
p3++;
}
while (p2 < s2.length() && p3 < s3.length() && s2.charAt(p2) == s3.charAt(p3)) {
p2++;
p3++;
}
if (p3 < s3.length() && ((p1 >= s1.length() && s2.charAt(p2) != s3.charAt(p3)) || (p1 < s1.length() && s1.charAt(p1) != s3.charAt(p3)))) {
return false;
}
}
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
这一题动态规划的表示思路应该是：
状态：使用dp[i][j]来表示s1[0,i]和s2[0,j]能否交错组成s3[0,i+j]
状态转移：
- 如果dp[i][j]为真，且s1[i+1]==s3[i+j+1]，则dp[i+1][j]为真
- 如果dp[i][j]为真，且s2[j+1]==s3[i+j+1]，则dp[i][j+1]为真
反过来说就是要得到当前的dp[i][j]
- 如果dp[i-1][j]为真且s1[i]=s3[i+j]，则dp[i][j]为真
- 如果dp[i][j-1]为真且s2[j]=s3[i+j]，则dp[i][j]为真
- 都不满足，则则dp[i][j]为假。
初始化dp[0][j]为s2[0,j]==s3[0,j]，（j<=s2.length），dp[i][0]为s1[0,i]==s3[0,i]，（i<s1.length）。
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length()+s2.length()!=s3.length()) return false;
int m=s1.length(),n=s2.length();
boolean[][] dp=new boolean[m+1][n+1];
//初始化边界值
dp[0][0]=true;
boolean b=true;
for (int j = 1; j <= n; j++) {
dp[0][j] = b && (b = (s2.charAt(j-1) == s3.charAt(j-1)));
}
b=true;
for (int i = 1; i <= m; i++) {
dp[i][0] = b && (b = (s1.charAt(i-1) == s3.charAt(i-1)));
}
//开始DP过程
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
}
}
return dp[m][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
上面的这两题的DP数组都是dp[m+1][n+1]，它们的第一行和第一列都是为了表示其中一个字符串为空时只靠另一个字符串进行处理的边界情况。这样使得dp数组的技术是从1开始的而不是0开始的，而String.charAt()是从0开始取，所以代码中出现了很多的-1，处理地不细心就可能出错，以后遇到还是在三个字符串前都加上一个占位字符来从1开始取吧。另外这两题都是可以优化空间的将二维dp数组将为一维（和昨天的62、63题一样），不过这些-1+1的下标这会儿实在看得人眼花……这次就偷个懒了。