动态规划无疑是最经典的问题类型之一,而二维动态规划的难度要高于之一维动规,但本质确一样。而最经典的二维动规题有,编辑距离,最长公共子序列,最长回文子序三个,而本文就带大家用二维动规来处理这三道题。
1. 编辑距离
这道题堪称二维动规中经典中的经典了,考查率很高!
但这题的套路本质和一维动规题基本一致
给两个字符串,str1,str2 要计算由str1变成str2至少需要操作几步,操作方式有三种,插入,删除,替换(每次只能操作一个字符)
如,str1="batman", str2="ironman" 输出应该是4,因为需要四步
- b替换成i
- a替换成r
- t替换成o
- 插入n
此时这道题最有意思的地方来了,bat 在变成 iron 时,怎么知道此时应该插入呢?由于后面的 man 是相同的,那显然 bat 在第四个步骤应该插入 n ,这样才是最佳步骤。所以,如何才能算得这点呢?
对于复杂问题,动规告诉我们要简化,把大问题大问题变小问题。
那么那这道题是否也可以简化?
首先我们要知道,对于动规问题,最重要的不仅是子问题,还要有终止点或起始点,比如斐波那契数列如果使用递归来做,那就要有 if n == 1 || n== 2 { return 1 }
这个终止点,但反过来,n == 1 和 n == 2
不也正是起始点么?
所以,这道题也需要找到起始点,那它的起始点在哪呢?
当我们把问题缩到最小,即字符串长度为0时,那会发生什么?
当str1长度为0时,那想要变成str2,那必然要一直执行插入操作。
反之,当str2为0时,那想要变成str2,就要一直执行删除操作。
所以,当有一个字符串为0时,则路径长度与另一个字符串长度相关,由此,二维动规的数组,第一行和第一列可得,那此时这道题的起始点就有了,这道题也就有的搞了。
s | . | b | a | t | m | a | n |
---|---|---|---|---|---|---|---|
. | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
i | 1 | ||||||
r | 2 | ||||||
o | 3 | ||||||
n | 4 | ||||||
m | 5 | ||||||
a | 6 | ||||||
n | 7 |
初始数组拿出来了,那接下来如何填其余的值呢?
以 dp[1][1] 为例,那 dp[1][1] 代表的含义是字符串 "b" 变成 "i" 需要的步骤,显然是 1,其实dp[i][j]相当于在之前的字符串(此时之前的字符串为两个空串)上各加一个字符,而这两个字符不同,因此也需要一次操作,而最小值自然是之前三个数的最小值加1.
那如果新增的字符与原字符串相同呢?dp[i][j] 在 str1[i] == str2[j]
的时候等于 dp[i-1][j-1]
, 那相当于没有新增字符,也就是和 str[i-1][j-1]时完全一至,因为新加的字符和之前完全相同,自然就等于没加之前的了。
由此,我们将数组补全。
s | . | b | a | t | m | a | n |
---|---|---|---|---|---|---|---|
. | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
i | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
r | 2 | 2 | 2 | 3 | 4 | 5 | 6 |
o | 3 | 3 | 3 | 3 | 4 | 5 | 6 |
n | 4 | 4 | 4 | 4 | 4 | 5 | 5 |
m | 5 | 5 | 5 | 5 | 4 | 5 | 6 |
a | 6 | 6 | 5 | 6 | 6 | 4 | 5 |
n | 7 | 7 | 6 | 6 | 7 | 5 | 4 |
动规方程如下:
最终程序如下:
func minDistance(word1 string, word2 string) int {
x, y := len(word1), len(word2)
if x == 0 { return y }
if y == 0 { return x }
// 初始化 dp 数组
dp := make([][]int, x + 1)
for i, _ := range dp {
dp[i] = make([]int, y + 1)
}
for i := 0; i <= x; i++ {
dp[i][0] = i
}
for i := 0; i <= y; i++ {
dp[0][i] = i
}
for i := 1; i <= x; i++ {
for j := 1; j <= y; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
// 这里省略了 min 函数
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
}
}
}
return dp[i][j]
}
2. 最长公共子序列(Longest Common Subsequence, LCS)
首先,这道题问的是子序列,例如 "abc" 的子序列就有 ["a", "b", "c", "ab", "ac", "bc", "abc"],而该题问的是两个字符串的最长公共子序列。
如有,str1="abcdef", str2="acdgk" 算法输出应该为3,两个字符串的最长公共子序列为 "acd"。
如果使用回溯算法,在逐一比较,那这个时间复杂度可以说是原地爆炸了。
那么在动规算法中,最重要的一点无疑是找到子问题。
同样是 abcdef 和 acdgk 比较,根据经验,我们先将字符串缩小比较范围,最小到哪呢,就是1个符时,a和a,那在增加 ab和ac ,abc和acd 以此类推。但仔细想想这么做也不行,因为单条线的dp无法准确的表示出这两个字符串的公共序列。
所以,二维动态规划就要登场了。
此时我们需要一个二维数组如下:
. | a | b | c | d | e | f | |
---|---|---|---|---|---|---|---|
. | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
a | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
d | 0 | 1 | 1 | 2 | 3 | 3 | 3 |
g | 0 | 1 | 1 | 2 | 3 | 3 | 3 |
k | 0 | 1 | 1 | 2 | 3 | 3 | 3 |
那这个数组表示了什么? dp[i][j] 表示 str1[:i] 与 str2[:j] 两个字符串的分段的最长公共子序,那问题来了,那为什么这个二维数组能求出LCS呢?
其实很简单,当 i,j = 0 时,就意味着至少有一个字符串是空串,那LCS必然为0,而当i,j均不为0时,且 str1[i] == str2[j] 就意味着相较之前,此时两个片段都新增了相同的字符,那此时LCS必然要加一,那如果 str1[i] != str2[j] 呢,那就意味着两个片段都加了一个不同的字符,LCS和之前的值一致,相当于没加。
最终可得出动态方程,即为:
那可能有人会有疑问,为什么只对比 $f(x-1,y)$ 和 $f(x,y-1)$ 而不对比 $f(x-1, y-1)$ 呢?那是因为 str1[:x-1],str2[:y-1] 是三个值当中两个字符串最短的,所以也必然是三个值中最小的,因此只用对比前两个值即可。
func LCS(str1, str2 string) int {
x, y := len(str1), len(str2)
if x == 0 || y == 0 {
return 0
}
// 初始化 dp
dp := make([][]int, x + 1)
for i, _ := range dp {
dp[i] = make([]int, y + 1)
}
for i := 1; i < x; i++ {
for j := 1; j < y; j++ {
if str1[i-1] == str2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
// max 函数这里省略了
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
}
}
}
return dp[x][y]
}
3. 最长回文子序列
又是一道子序列题,该题意思是,给一个字符串str,要找出该字符串的最长回文子序列,注意是子序列!
例如:字符串 str 为 "adcqcia" 那么最长回文子序列应该是 "acqca",所以答案是5。
那该题与前两题不同。该题只有一个字符串,怎么会是二维的动态规划呢?
其实,回文不就是正反读都一样么?那找回文子序列,不就是找正反两个字符串的最长子序嘛?
如 adcqcia 与 aicqcda 的最长子序列,不就是本题答案了么?
所以,该题其实是上一题的变种。本质无区别。
. | a | d | c | q | c | i | a | |
---|---|---|---|---|---|---|---|---|
. | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
a | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
i | 0 | 1 | 1 | 1 | 1 | 1 | 2 | 2 |
c | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 2 |
q | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 3 |
c | 0 | 1 | 1 | 2 | 3 | 4 | 4 | 4 |
d | 0 | 1 | 2 | 2 | 3 | 4 | 4 | 4 |
a | 0 | 1 | 2 | 2 | 3 | 4 | 4 | 5 |
动态方程略有变化:
而本题代码和上题基本一致
func longestPalindromeSubseq(s string) int {
x := len(s)
if x == 0 {
return 0
}
// 初始化 dp
dp := make([][]int, x + 1)
for i, _ := range dp {
dp[i] = make([]int, x + 1)
}
for i := 1; i <= x; i++ {
for j := 1; j <= x; j++ {
if s[i-1] == s[x-j] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
// max 函数这里省略了
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
}
}
}
return dp[x][y]
}
结语
二维动态规划还是很锻炼思维的,虽然题做起来不难,但还是要理解动态规划的思考方式,只有学会了思考方式,才能获益万分。