专题 23动态规划高阶：区间、树形与状态压缩

23.1进阶 DP 只是把状态定义变复杂

先打消畏难情绪。无论状态多花哨，五步法的骨架一字未改：

一个统一的心法

不管维度怎么升，问自己的永远是两句老话：「dp 数组的每个格子代表什么？」「这个格子的值，能由哪些更小的格子推出来？」 区间 DP 里「更小」是「更短的区间」，树形 DP 里「更小」是「更浅的子树」，状压里「更小」是「更少元素的集合」。抓住这条线，三类都能拆。

23.2最长回文子序列：区间 DP（中等，力扣 516）

中等 核心：dp[i][j] + 遍历方向

题意：给定字符串 s，求它的最长回文子序列的长度（子序列 = 可以删字符、不要求连续）。例：s = "bbbab" → 最长回文子序列是 "bbbb"（取第 1、2、3、5 个字符），长度 4。

思路推导

第一步，明确「子序列」和「子串」的天壤之别。21.2 节的最长回文子串要求连续，用中心扩展 O(1) 空间就搞定。但子序列不连续，中心扩展彻底失效——你得决定「跳过哪些字符」。这正是区间 DP 的舞台。

第二步，定义状态。令 dp[i][j] = 子串 s[i..j] 中最长回文子序列的长度。答案就是 dp[0][n-1]。

第三步，转移方程——看两端字符。对区间 [i, j]：

• 若 s[i] == s[j]：这两个字符可以同时作为回文的两端，于是 dp[i][j] = dp[i+1][j-1] + 2（中间那段的最长，加这一对）；
• 若 s[i] != s[j]：至少得丢掉一端，取「丢左」和「丢右」的较大者：dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

第四步，遍历顺序为什么 i 从后往前。注意转移依赖 dp[i+1][...] 和 dp[i][j-1]——也就是左下方和正下方的格子。所以必须保证「算 dp[i][j] 时，它左下/下方的格子已经算好」。做法：i 从 n-1 倒着往 0 走，j 从 i+1 顺着往 n-1 走（j 永远大于 i，区间长度从小变大）。这样每个 dp[i][j] 依赖的更短区间都先填完。边界：i == j 时 dp[i][i] = 1（单字符本身是回文）。

参考代码

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        // 单字符区间：长度 1 的回文子序列长度为 1
        for (int i = 0; i < n; i++) dp[i][i] = 1;

        // i 从后往前，j 从 i+1 往后；保证依赖的更短区间先算
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;   // 两端相同，包起来
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // 丢一端
                }
            }
        }
        return dp[0][n - 1];                    // 整串的最长回文子序列
    }
}

复杂度

O(n²) 时间（两重循环），O(n²) 空间（二维表）。对比中心扩展求子串是 O(n²) 时间 O(1) 空间——但子序列问题中心扩展干不了，DP 是标准解。

23.3戳气球：区间 DP（困难，力扣 312，选学）

困难 核心：反向思维 + 开区间 选学

题意：有 n 个气球排成一排，第 i 个分值 nums[i]。戳破气球 i 时，获得 nums[left] * nums[i] * nums[right] 分（left, right 是它此时左右相邻的气球）。戳完所有气球求最大总分。例：nums = [3,1,5,8] → 最大 167。

思路推导

第一步，正向想为什么难。「先戳哪个」会影响后续相邻关系，状态互相缠绕，正向 DP 极难定义——戳破一个，数组就变了。

第二步，反向思维——「最后戳哪个」。换个角度：与其想「先戳谁」，不如想「最后被戳的是谁」。在最后一步，[i, j] 区间内只剩一个气球 k 没戳，它的左右边界是「区间外的 i-1 和 j+1」（这两个此时已经固定、不再变）。所以戳 k 得分 nums[i-1]*nums[k]*nums[j+1]。那么 [i, j] 的最大得分 = 左半 [i, k-1] 的最大 + 右半 [k+1, j] 的最大 + 这一步得分。

第三步，开区间 dp[i][j]。定义 dp[i][j] = 戳破开区间 (i, j) 内所有气球（不含 i、j 本身）能获得的最大分数。这里 i、j 是「虚拟边界」，永远不会被戳，只作为乘数存在。为处理首尾，在 nums 首尾各补一个 1（如 [1,3,1,5,8,1]），让任何区间都有合法左右邻居。

第四步，转移：dp[i][j] = max over k∈(i,j) of (dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])。遍历顺序同样是 i 从后往前、j 从 i+1 往后（依赖更短开区间）。

参考代码（选学，看懂思想即可）

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] a = new int[n + 2];            // 首尾补 1
        a[0] = 1; a[n + 1] = 1;
        for (int i = 0; i < n; i++) a[i + 1] = nums[i];

        int[][] dp = new int[n + 2][n + 2];  // dp[i][j]: 开区间(i,j)最大分
        // i 从后往前，j 从 i+1 往后，区间长度逐渐增大
        for (int i = n; i >= 1; i--) {
            for (int j = i + 1; j <= n + 1; j++) {
                for (int k = i + 1; k < j; k++) {   // 最后戳 k
                    int gain = a[i] * a[k] * a[j];   // 此时左右邻居是 i 和 j
                    dp[i][j] = Math.max(dp[i][j],
                                        dp[i][k] + dp[k][j] + gain);
                }
            }
        }
        return dp[0][n + 1];                  // 开区间(0, n+1)即全部
    }
}

复杂度

O(n³) 时间（三重重循环），O(n²) 空间。第一次学可跳过；它展示的「反向定义最后一步」是区间 DP 的高级套路。

23.4打家劫舍 III：树形 DP（中等，力扣 337）

中等 核心：每个节点返回「偷/不偷」两值

题意：房子排成二叉树结构，不能偷直接相连的两户（父子不能同时偷）。求能偷到的最大金额。例：[3,2,3,null,3,null,1] → 偷根 3 + 右孙 3 + 右右孙 1 = 7，返回 7。

思路推导

第一步，承接到线性版。专题 09 的打家劫舍是在数组上：dp[i] 表示「前 i 户最大」，转移 dp[i]=max(偷i+不偷i-1, 不偷i=dp[i-1])。现在结构从「数组」变成「树」，思路完全类比，只是遍历方式换成了后序遍历。

第二步，每个节点返回两个值。对任一节点，我们必须知道「偷它」和「不偷它」两种情况各自的最大收益，因为父节点需要根据子节点的这两种值做决定。所以设计：递归返回 int[2]，[0] = 不偷当前节点的最大收益，[1] = 偷当前节点的最大收益。

第三步，转移（后序）。先递归算左右子树各自的 [偷, 不偷]，再组合：

• 偷当前节点：则左右孩子都不能偷 → val + left[0] + right[0]；
• 不偷当前节点：左右孩子偷不偷都行，各取 max → max(left[0],left[1]) + max(right[0],right[1])。

后序遍历保证「先算出孩子、再算自己」，天然契合「子问题优先」。

参考代码

class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);     // 根偷或不偷取大
    }

    // 返回 int[2]： [0]=不偷当前节点的最大收益, [1]=偷当前节点的最大收益
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};   // 空节点两值皆 0
        int[] left = dfs(node.left);       // 后序：先递归左右子树
        int[] right = dfs(node.right);

        int robHere = node.val + left[0] + right[0];        // 偷：孩子都不能偷
        int skipHere = Math.max(left[0], left[1])
                      + Math.max(right[0], right[1]);       // 不偷：孩子取各自最大
        return new int[]{skipHere, robHere};
    }
}

复杂度

O(n) 时间（每个节点访问一次），O(h) 空间（递归栈，h 为树高）。把「数组 DP」原封不动地翻译成「树上后序 + 返回双值」即可。

23.5优美的排列：状态压缩 DP（中等，力扣 526）

中等 核心：bitmask 表示已选集合

题意：给定 n，构造一个 1~n 的排列 nums，要求对每个位置 i（1-indexed），nums[i] 能被 i 整除，或 i 能被 nums[i] 整除。求满足条件的排列个数。例：n=2 → [1,2] 和 [2,1] 都满足，返回 2。

思路推导

第一步，为什么必须状压。暴力枚举所有排列是 n! 种——n=15 时 15! ≈ 1.3×10¹²，直接爆。但注意到 n≤15，而「哪些数字已经被选」只有 2ⁿ 种状态（2¹⁵=32768），完全可枚举。用二进制位表示「已选集合」，把指数级的排列压成多项式级的子集，这就是状态压缩 DP。

第二步，定义状态。设 dp[mask] = 用掉 mask 所表示的数字集合后，能形成的合法排列个数。其中 mask 的第 k 位为 1 表示数字 k+1 已被选（位运算技巧见 专题 14）。

第三步，转移——一位一位填。当前已选集合 mask，意味着已经填好了前 cnt 个位置（cnt = mask 中 1 的个数，即 Integer.bitCount(mask)）。下一个要填的是第 cnt+1 个位置。枚举还没选的数字 num（即 mask 中为 0 的位），若 num 与位置 cnt+1 满足整除条件，则可以从 dp[mask] 转移到 dp[mask | (1< 并累加。

class Solution {
    public int countArrangement(int n) {
        int full = 1 << n;                    // 状态总数 2^n
        int[] dp = new int[full];
        dp[0] = 1;                            // 空集：一种起点

        for (int mask = 0; mask < full; mask++) {
            int cnt = Integer.bitCount(mask);  // 已填的位置数 = 已选数字数
            if (cnt >= n) continue;            // 填满了不用再扩
            int pos = cnt + 1;                 // 下一个要填的位置（1-indexed）
            for (int num = 1; num <= n; num++) {
                int bit = 1 << (num - 1);
                if ((mask & bit) != 0) continue;          // num 已选过，跳过
                // 整除条件：num 被 pos 整除，或 pos 被 num 整除
                if (num % pos == 0 || pos % num == 0) {
                    dp[mask | bit] += dp[mask];           // 转移并累加
                }
            }
        }
        return dp[full - 1];                   // 全选完的排列数
    }
}

class Solution {
    int[][] memo;                    // 缓存：从 (x,y) 出发的最长递增路径
    int[][] matrix;
    int m, n;
    int[][] dirs = {{-1,0},{0,1},{1,0},{0,-1}};

    public int longestIncreasingPath(int[][] matrix) {
        this.matrix = matrix;
        m = matrix.length; n = matrix[0].length;
        memo = new int[m][n];        // 初始 0 表示未算（长度至少 1，不会冲突）
        int ans = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                ans = Math.max(ans, dfs(i, j));   // 每个点都当一次起点
        return ans;
    }

    private int dfs(int x, int y) {
        if (memo[x][y] != 0) return memo[x][y];    // 算过直接返回（缓存命中）
        int best = 1;                               // 至少包含自己
        for (int[] d : dirs) {
            int nx = x + d[0], ny = y + d[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n
                && matrix[nx][ny] > matrix[x][y]) { // 只走严格更大的邻居
                best = Math.max(best, 1 + dfs(nx, ny));
            }
        }
        memo[x][y] = best;                          // 存回缓存
        return best;
    }
}