从一道dp算法题说起

Sat ,Feb 24 ,2018

被这道leetcode题目516. Longest Palindromic Subsequence折腾良久，直到最后弄清楚它，才大呼奇妙。算法与思维的神奇，大概就在此处。

这篇文章不错，可以作为入门。

1.题目分析

动态规划的关键就是得出状态与状态转移方程。

这道题我的第一个问题就是：没有想清楚，为什么它是一个二维的状态?

一维与二维的区别就在于状态之间的转换。
对于这道题而言，以一个字符为例，它可以通过左边增加字符或者右边增加字符，进入下一个状态.
由现有的状态有超过1种途径进入下一个状态。因为它是二（多）维的。

这道题的状态转移方程如下：

dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j)
otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
Initialization: dp[i][i] = 1

2.代码分析。

看到上面的状态转移方程，很容易就可以得到递归的办法。

func longestPalindromeSubseq(s string) int {
    return check([]byte(s)) 
}

func check(s []byte) int {
    if s[0] == s[len(s)-1] {
        return 2 + check(s[1:len(s)-1])
    }else {
        a := check(s[0:len(s)-1])
        b := check(s[1:len(s)])
        if b > a {
            a = b
        }
        return a
    }
}

这样是过不了的。加上缓存，去掉重复的计算，accepted.

接下来，其实也就是一个递归转化成循环的问题。按照上述的状态转移方程，以abcd为例，要算abcd,必须先算出abc和bcd,则必须先算出ab,bc,cd，则必须先算出a,b,c,d。单个字符已知就是1.所以，可以得到以下的代码。

func longestPalindromeSubseq(s string) int {
    n := len(s)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][i] = 1
    }

    for Len := 2; Len <= n; Len++ {
        for i := 0; i+Len-1 < n; i++ {
            j := i + Len - 1
            if s[i] == s[j] {
                dp[i][j] = dp[i+1][j-1] + 2
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
            }
        }
    }

    return dp[0][n-1]
}

进一步，研究状态转移方程，可以发现dp[i][j]只与dp[i+1][j-1],dp[i+1][j], dp[i][j-1]这几个量有关系，即要算出i，须先算出i+1.要算出j,须先算出j-1. 同时，想象一个二维的长方形，我们知道对角线上的每一个值。

每一个位置表示： 从本行左侧为1的字符起，到该字符位置的最大的回文字符个数。
| 1| c| c| c| // i层第四次循环 j层循环三次
|  | 1| b| b| // i层第三次循环 j层循环二次
|  |  | 1| a| // i层第二次循环 j层循环一次
|  |  |  | 1| // i层第一次循环 j层循环跳出

因此，双层循环嵌套，i由大变小，j由小变大。

dp := make([]int, n)
cur := make([]int, n)

for i := length-1;i >= 0; i-- {
    cur[i] = 1
    for j := i+1; j < length; j++ {
        if s[i] == s[j] {
            // 最是神奇的一步
            cur[j] = dp[j-1] + 2
        }else {
            cur[j] = max(cur[j-1],dp[j])
        }
    }
    dp, cur = cur, dp
}

最后两份代码，只是循环的方式不同而已。代码二是可以采用代码三的双数组缓存去优化的。

直到最终的代码出来，才发现，最终的代码就是最开始状态转移方程最原始的体现。简单即是大美。

Diamondu

从一道dp算法题说起