动态规划专栏

参考书籍：《labuladong的算法小抄》
ISBN： 9787121399336

DP之道

Dynamic Programming是困扰我许久的问题，结合解题框架和刷题情况想开一期专栏专门记录一下。
首先，DP问题的表现形式一般是求最值问题。 如，最长回文子串，最长递增子序列、最小编辑距离等。
其次，DP的核心思想是穷举法。 但这个穷举不是暴力穷举，而是需要借助 dp table等来优化穷举过程，避免不必要的计算。
最后，正确穷举需要借助正确的“状态转移方程”。 状态转移方程这个高端的名词，实质上就是类似于 f(n) = f(n-1) + f(n-2)这样的递推表达式，相当于是从前两个状态推出现在的状态。但状态转移方程在不同问题中有不同的表现形式。

东哥给出的解题框架：

# 初始化base case
dp[0][0][...] = basecase
# 状态转移
for 状态1 in 状态1的所有取值:
	for 状态2 in 状态2的所有取值:
		for ...
			dp[状态1][状态2][...] = 求最值(选择1,选择2,...)
1
2
3
4
5
6
7

关注点：最简单的情况是什么（base case），怎么定义状态，怎么定义选择。

DP之术

5.最长回文子串

子串和子序列有一个区别，子串必须是连续的，子序列不必连续。

回文串的特点是回文串开头和结尾一定是相同的字符，且去掉头尾后仍是回文串。
利用这个特点构造dp数组

int len = str.length();
boolean[][] dp = new boolean[len][len];
1
2

例如，dp[ i ][ j ]表示数组下标 i 到 j 之间是否是回文串。
base case是所有单个字符如dp[1][1]、dp[2][2]都为true，因为一个字符肯定是回文串。
状态转移方程是：

dp[i][j] = dp[i+1][j-1]
1

相当于将头尾去掉，剩下的也应该是回文串才能保证 i 到 j 之间都是回文串。
返回的子串根据下标索引给出：

return str.substring(begin, begin + maxlen);
1

完整代码如下：

class Solution {
    public String longestPalindrome(String s) {
       int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxlen = 1; // 最长长度
        int begin = 0;

        // dp[i][j]表示s[i...j]是否是回文串
        boolean[][] dp = new boolean[len][len];

        char[] charArr = s.toCharArray();
        // 递推:L是回文串长度，i是左边界
        for (int L = 2; L <= len; L++) {
            for (int i = 0; i < len; i++) {
                int j = i + L - 1; // j是右边界
                // 右边界越界时退出循环
                if (j >= len) break;
            

                // 回文串的左右边界应相等
                if (charArr[i] != charArr[j]) {
                    dp[i][j] = false;
                } else {
                    if (L < 4) { // 回文串长度小于4时（2或3） 
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                if (dp[i][j] == true && L > maxlen) {
                    maxlen = L;
                    begin = i;
                }
            }
        }

        return s.substring(begin, begin + maxlen);
    }
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42