动态规划

Those who do not remember the past are condemned to repeat it.

理论

  • 特点
    • 重复子问题：需要记录之前的计算结果；
    • 最优子结构：不同规模之间的关系；
    • 后无效性：只记录阶段结果而不关心这个结果是怎么来的；
  • 思路方向
    • 自顶向下：递归+记忆化；
    • 自底向上：递推求解。
  • 状态转移方程
    • 将当前问题分解为几个小问题，这些小问题的最优解构成当前问题的最优解；
  • 初始化
  • 输出
    • 有时题目的解并不是最后一个状态
  • 考虑是否有可优化空间

例题

最长回文子串

题目：
给你一个字符串 s，找到 s 中最长的回文子串。

1
2
3
4
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
1
2
3
示例 2：
输入：s = "accacc"
输出："ccacc"

解题思路：

状态转移方程

  • 对于一个长度大于2的子串而言，如果他是回文串，那么它的首尾字符相同且去掉首尾两个字符，它任然是个回文串。
  • 使用f(i, j)表示字符串s从第i个字符到第j个字符所组成的字符串 ，f(i, j)是回文串等价 于 f(i + 1, j - 1)是回文串且s[i] 和 s[j]相等。 根据这样的思路可以得出他的状态转移方程：
    1
    f(i,j) = f(i + 1, j - 1) ∧ (s[i]== s[j])

初始化

  • 对于长度大于3的状态可以使用状态转移方程，对于长度为1的字符串，它肯定是一个回文串；对于长度为2的字符串，当两个字符相同即s[i] = s[i+1]时，它是一个回文串，所以可得出初始化：
    1
    2
    3
    f(i, i) = true

    f(i, i+1) = (s[i] == s[i + 1])

思考输出

  • 我们需要求出的结果是最长回文串，是整个计算过程中的某一个状态，并不一定是是递归到最后一层所得出的结果。
  • 设置maxLength = 0， 每当计算出一个状态且子串长度大于maxLength时更新maxLength的值并记录子串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String longestPalindrome(String s) {
    int maxLength = 0;
    String result = "";
    boolean[][] dp = new boolean[s.length()][s.length()];
    for (int j = 0; j < s.length(); ++j) {
        for (int i = 0; i < j + 1; ++i) {
            if (i == j) {
                dp[i][j] = true;
            } else if (j - i == 1) {
                dp[i][j] = (s.charAt(i) == s.charAt(j));
            } else {
                dp[i][j] = dp[i + 1][j - 1] && (s.charAt(i) == s.charAt(j));
            }
            if (dp[i][j] && j - i + 1 > maxLength) {
                maxLength = j - i + 1;
                result = s.substring(i, j + 1);
            }
        }
    }
    return result;
}

复杂度分析：二维 dp 问题，一个状态得用二维有序数对表示。

1
2
3
时间复杂度：O(N^{2})

空间复杂度：O(N^{2})