经典二维动态规划

动态规划无疑是最经典的问题类型之一，而二维动态规划的难度要高于之一维动规，但本质确一样。而最经典的二维动规题有，编辑距离，最长公共子序列，最长回文子序三个，而本文就带大家用二维动规来处理这三道题。

1. 编辑距离

这道题堪称二维动规中经典中的经典了，考查率很高！
但这题的套路本质和一维动规题基本一致

给两个字符串，str1,str2 要计算由str1变成str2至少需要操作几步，操作方式有三种，插入，删除，替换（每次只能操作一个字符）
如，str1="batman", str2="ironman" 输出应该是4，因为需要四步

1. b替换成i
2. a替换成r
3. t替换成o
4. 插入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时，则路径长度与另一个字符串长度相关，由此，二维动规的数组，第一行和第一列可得，那此时这道题的起始点就有了，这道题也就有的搞了。

初始数组拿出来了，那接下来如何填其余的值呢？

以 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]时完全一至，因为新加的字符和之前完全相同，自然就等于没加之前的了。
由此，我们将数组补全。

动规方程如下：

最终程序如下：

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无法准确的表示出这两个字符串的公共序列。

所以，二维动态规划就要登场了。
此时我们需要一个二维数组如下：

那这个数组表示了什么？ 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 的最长子序列，不就是本题答案了么？
所以，该题其实是上一题的变种。本质无区别。

动态方程略有变化：

而本题代码和上题基本一致

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]
}

结语

二维动态规划还是很锻炼思维的，虽然题做起来不难，但还是要理解动态规划的思考方式，只有学会了思考方式，才能获益万分。