第八章：动态规划高级——区间DP、树形DP与经典例题

动态规划学到这儿，大家基本套路都熟了。但说实话，面试里真正卡人的，往往是那些「状态定义不直观」的题目。今天聊的区间DP和树形DP，就是这类问题的典型代表。

我个人习惯把区间DP叫做「小区间推大区间」的玩法。而树形DP，说白了就是在树上做递归决策。这两个东西看着唬人，其实核心思想没变——还是那个「最优子结构 + 重叠子问题」的老配方。

8.1 区间DP：从小区间开始，慢慢长大

区间DP，顾名思义，状态是一个区间。比如 dp[i][j] 表示从第 i 个元素到第 j 个元素这个区间的最优解。怎么转移？通常是在区间里找一个分割点 k，把大区间拆成两个小区间，然后合并结果。

我在项目中遇到过类似场景：要计算一段文本里最长的对称子串。当时第一反应是暴力枚举，但数据量一大就扛不住了。后来换成区间DP，复杂度从 O(n³) 降到 O(n²)，效果立竿见影。

8.1.1 经典例题：最长回文子串

题目很简单：给你一个字符串 s，找出其中最长的回文子串。回文就是正着读反着读都一样，比如 "aba"、"abba"。

嗯，这里要注意：回文子串有两种情况——奇数长度和偶数长度。区间DP可以统一处理。

状态定义：

dp[i][j] 表示子串 s[i..j] 是否为回文串（true/false）。

转移方程：

if s[i] == s[j]:
    if j - i <= 2:          // 长度小于等于3，直接是回文
        dp[i][j] = true
    else:
        dp[i][j] = dp[i+1][j-1]  // 取决于内部子串
else:
    dp[i][j] = false

代码实现：

public String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int start = 0, maxLen = 1;

    // 所有长度为1的子串都是回文
    for (int i = 0; i < n; i++) dp[i][i] = true;

    // 按长度从小到大枚举
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                if (len <= 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i+1][j-1];
                }
            }
            // 更新答案
            if (dp[i][j] && len > maxLen) {
                start = i;
                maxLen = len;
            }
        }
    }
    return s.substring(start, start + maxLen);
}

8.2 树形DP：在树上做决策

树形DP，就是把DP搬到了树上。你想想看，树的结构天然适合递归——每个节点的问题可以交给它的子节点去解决。状态通常定义成 dp[node][状态]，表示以 node 为根的子树在某种状态下的最优解。

我个人觉得树形DP最妙的地方在于：它把「选或不选」这种二维决策，和树的层次结构完美结合在了一起。

8.2.1 经典例题：打家劫舍III

题目背景：小偷又来了。这次不是一排房子，而是一棵二叉树。每个节点代表一个房子，里面有现金。如果两个直接相连的房子同时被偷，会触发警报。问最多能偷多少钱。

说白了，这就是一个「相邻节点不能同时选」的问题，只不过从线性结构变成了树形结构。

状态定义：

每个节点有两个状态：

• dp[node][0]：不偷 node 时，以 node 为根的子树能偷到的最大值
• dp[node][1]：偷 node 时，以 node 为根的子树能偷到的最大值

转移方程：

// 不偷当前节点：子节点可偷可不偷，取大的
dp[node][0] = max(dp[left][0], dp[left][1]) + max(dp[right][0], dp[right][1])

// 偷当前节点：子节点都不能偷
dp[node][1] = node.val + dp[left][0] + dp[right][0]

代码实现：

public int rob(TreeNode root) {
    int[] result = dfs(root);
    return Math.max(result[0], result[1]);
}

private int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};

    int[] left = dfs(node.left);
    int[] right = dfs(node.right);

    // 不偷当前节点
    int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    // 偷当前节点
    int rob = node.val + left[0] + right[0];

    return new int[]{notRob, rob};
}

8.3 知识体系总览

下面这张图总结了区间DP和树形DP的核心要点。我建议你把它存下来，刷题前看一眼，思路会清晰很多。

8.4 总结与避坑

区间DP和树形DP，说白了就是两种特殊的DP场景。区间DP的关键在于「枚举长度」和「枚举分割点」的顺序；树形DP的关键在于「后序遍历」和「多状态返回」。

最后分享几个我踩过的坑：

• 区间DP的初始化： 长度1的区间一定要先初始化好，否则后面转移会出问题。
• 树形DP的递归边界： 空节点返回 [0, 0] 是标准写法，别漏了。
• 状态数组的维度： 区间DP常用二维数组，树形DP常用一维数组+状态枚举。别搞混了。

嗯，这一章的内容就到这儿。记住：多画图、多手动推状态，比死记硬背代码管用得多。

---

公众号：蓝海资料掘金营，微信 deep3321