区间 DP：戳气球、矩阵链乘与「从小区间到大区间」

摘要

区间 DP 是动态规划中最具”反直觉”气质的一类题型。它的状态是一段区间 [i, j]，转移是枚举区间内的分割点 k，把大区间分解为小区间的子问题。最反直觉的地方在于：你需要先解决小区间，再解决大区间，这意味着遍历顺序不再是”从左到右”，而是”从短到长”——先枚举区间长度，再枚举起点。本文通过矩阵链乘（经典教材引入）、戳气球（LeetCode 312）、奇怪的打印机（LeetCode 664）三道题，帮助你彻底理解区间 DP 的建模技巧和遍历框架。

第 1 章区间 DP 的核心框架

1.1 什么是区间 DP

区间 DP 的基本特征：

状态是一段区间：dp[i][j] 表示对区间 [i, j] 进行某种操作（合并、分割、删除）的最优代价
转移是枚举分割点：把 [i, j] 在某个位置 k 处拆分，得到 [i, k] 和 [k+1, j] 两个子区间，状态转移方程形如：

$d p [i] [j] = min_{k = i}^{j - 1} f (d p [i] [k], d p [k + 1] [j], 合并代价)$

依赖关系是「小区间先于大区间」：计算 dp[i][j] 时，需要所有包含在 [i, j] 内的子区间已经计算完毕

1.2 遍历顺序：为什么要按区间长度枚举

错误的遍历方式（按起点枚举）：

// ❌ 错误：外层枚举起点 i
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = i; k < j; k++) {
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
        }
    }
}

问题：当计算 dp[0][3] 时，需要 dp[0][2]（已有）和 dp[1][3]（还没算！因为起点 1 的外层循环还没到）。

正确的遍历方式（按区间长度枚举）：

// ✅ 正确：外层枚举区间长度 len
for (int len = 2; len <= n; len++) {          // 区间长度从 2 开始（长度 1 是 base case）
    for (int i = 0; i + len - 1 < n; i++) {  // 枚举起点 i
        int j = i + len - 1;                  // 终点 j = i + len - 1
        dp[i][j] = Integer.MAX_VALUE;
        for (int k = i; k < j; k++) {         // 枚举分割点 k
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i, k, j));
        }
    }
}

保证：外层先计算所有长度为 len-1 的区间，再计算长度为 len 的区间。长度为 len 的区间 [i,j] 依赖的所有子区间（[i,k] 和 [k+1,j]，长度均 < len）已经计算完毕。

1.3 区间 DP 的模板代码

int n = ...; // 元素个数
int[][] dp = new int[n][n];
 
// 初始化：长度为 1 的区间（base case）
for (int i = 0; i < n; i++) {
    dp[i][i] = baseCaseValue(i);
}
 
// 枚举区间长度（从 2 到 n）
for (int len = 2; len <= n; len++) {
    for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;
        dp[i][j] = Integer.MAX_VALUE; // 或 0，取决于是最小值还是最大值
        // 枚举分割点 k
        for (int k = i; k < j; k++) {
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + merge(i, k, j));
        }
    }
}
 
// 答案
return dp[0][n - 1];

时间复杂度： $O (n^{3})$ （三层循环：区间长度 × 起点 × 分割点）。空间复杂度： $O (n^{2})$ 。

第 2 章矩阵链乘：区间 DP 的经典引入

2.1 问题描述

给定 n 个矩阵 $A_{1}, A_{2}, \dots, A_{n}$ ，其中矩阵 $A_{i}$ 的维度为 $p_{i - 1} \times p_{i}$ 。矩阵乘法满足结合律： $(A_{1} A_{2}) A_{3} = A_{1} (A_{2} A_{3})$ ，但不同的结合方式导致的乘法次数不同。求最少需要多少次标量乘法？

例子：三个矩阵 $A (10 \times 30) \times B (30 \times 5) \times C (5 \times 60)$ ：

方案一： $(A B) C$ ： $10 \times 30 \times 5 + 10 \times 5 \times 60 = 1500 + 3000 = 4500$
方案二： $A (BC)$ ： $30 \times 5 \times 60 + 10 \times 30 \times 60 = 9000 + 18000 = 27000$

两种方案差了 6 倍！最优加括号方式对性能影响巨大。

2.2 区间 DP 建模

状态：dp[i][j] = 计算矩阵乘积 $A_{i} \times A_{i + 1} \times \dots \times A_{j}$ 的最少标量乘法次数。

Base Case：dp[i][i] = 0（单个矩阵，不需要乘法）。

转移方程：在位置 k 处分割，先计算 $A_{i} \dots A_{k}$ ，再计算 $A_{k + 1} \dots A_{j}$ ，最后合并（合并代价 = $p_{i - 1} \times p_{k} \times p_{j}$ ）：

$d p [i] [j] = min_{k = i}^{j - 1} (d p [i] [k] + d p [k + 1] [j] + p_{i - 1} \times p_{k} \times p_{j})$

public int matrixChainMultiplication(int[] p) {
    int n = p.length - 1; // n 个矩阵
    int[][] dp = new int[n][n];
    // dp[i][i] = 0（已默认）
 
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                // A[i..k] 和 A[k+1..j] 合并的代价是 p[i] * p[k+1] * p[j+1]
                int cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n - 1];
}

矩阵链乘是区间 DP 的”教科书案例”——状态含义直观，合并代价公式清晰，是理解区间 DP 框架的最佳起点。

第 3 章 LeetCode 312：戳气球

3.1 题目

LeetCode 312 - Burst Balloons（困难）

有 n 个气球，编号为 0 到 n-1，每个气球上都标有一个数字 nums[i]。每次戳破气球 i，得到 nums[i-1] * nums[i] * nums[i+1] 枚硬币（相邻气球的乘积）。戳破后气球消失，原来相邻的气球变为新邻居。

求能获得的最多硬币数。

输入: nums = [3, 1, 5, 8]
输出: 167
解释: nums = [3,1,5,8] → [3,5,8] → [3,8] → [8] → []
     硬币 = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

3.2 正向思考为什么失败

暴力： $O (n!)$ 种戳破顺序，每种顺序 $O (n)$ 时间计算，总共 $O (n! \times n)$ ，不可行。

尝试正向区间 DP：dp[i][j] = 戳破区间 [i, j] 内所有气球的最大硬币数，转移时枚举”第一个戳破的气球 k”。

问题：戳破 k 后，k 两侧的气球会合并，计算 k 的硬币需要知道 k 戳破时的邻居——但这取决于 [i, k-1] 和 [k+1, j] 中哪些气球已经被戳破，导致子问题之间不独立。

3.3 反向思维：「最后一个被戳破的气球」

关键洞察：从”第一个戳破”改为”最后一个戳破”的视角。

在区间 [i, j] 中，设 k 是最后一个被戳破的气球。那么：

在 k 被戳破之前，[i, k-1] 和 [k+1, j] 中的气球已经全部被戳破
因此当 k 被戳破时，它的邻居是区间 [i, j] 之外的气球——即i-1 号和 j+1 号
k 被戳破时获得的硬币：nums[i-1] * nums[k] * nums[j+1]（固定！不依赖中间顺序）

这样，子问题 [i, k-1] 和 [k+1, j] 就相互独立了（它们内部的戳破不会影响彼此边界的硬币）。

3.4 在两端加哨兵

在 nums 两端各加一个 1（nums[-1] = nums[n] = 1），这样边界气球的邻居是 1，简化代码。

设新数组 arr = [1, nums[0], nums[1], ..., nums[n-1], 1]，长度 n+2。

状态：dp[i][j] = 戳破开区间 (i, j) 内所有气球的最大硬币数（不包含 i 和 j 这两个哨兵）。

转移：枚举 (i, j) 内最后被戳破的气球 k：

$d p [i] [j] = max_{k = i + 1}^{j - 1} (d p [i] [k] + d p [k] [j] + a rr [i] \times a rr [k] \times a rr [j])$

注意：区间是开区间，k 的范围是 (i, j) 内部，即 i+1 <= k <= j-1。

Base Case：dp[i][i+1] = 0（相邻的两个哨兵之间没有气球）。

public int maxCoins(int[] nums) {
    int n = nums.length;
    // 构建带哨兵的数组
    int[] arr = new int[n + 2];
    arr[0] = arr[n + 1] = 1;
    for (int i = 0; i < n; i++) arr[i + 1] = nums[i];
 
    int size = n + 2;
    int[][] dp = new int[size][size];
 
    // 枚举区间长度（至少为 2，即区间内至少有 1 个气球）
    // 开区间 (i, j) 内有气球的条件是 j - i >= 2
    for (int len = 2; len < size; len++) {
        for (int i = 0; i + len < size; i++) {
            int j = i + len;
            // 枚举最后被戳破的气球 k
            for (int k = i + 1; k < j; k++) {
                // k 是开区间 (i, j) 内最后一个气球
                // 戳破 k 时，其邻居是 arr[i] 和 arr[j]
                int coins = arr[i] * arr[k] * arr[j];
                dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + coins);
            }
        }
    }
 
    // 答案是开区间 (0, n+1) 的结果（包含全部真实气球）
    return dp[0][n + 1];
}

时间复杂度： $O (n^{3})$ 。空间复杂度： $O (n^{2})$ 。

3.5 建模技巧总结

戳气球是区间 DP 中最经典的”逆向思维”题：

正向思维	逆向思维
枚举第一个戳破的	枚举最后一个戳破的
子问题不独立（边界会变）	子问题独立（最后被戳时边界固定）
无法用区间 DP 建模	完美契合区间 DP 框架

核心技巧：「最后一个操作」的枚举技巧

在区间 DP 中，如果枚举”第一个”操作导致子问题不独立，尝试改为枚举”最后一个”操作。后者的好处是：当最后一步发生时，其依赖的环境（边界）已经固定，子问题之间没有相互影响。

第 4 章 LeetCode 664：奇怪的打印机

4.1 题目

LeetCode 664 - Strange Printer（困难）

有一台奇怪的打印机，每次打印操作可以打印一段连续的字符，且每次打印都必须使用同一个字符（覆盖之前已有的内容）。求打印字符串 s 最少需要多少次操作。

输入: s = "aaabbb"
输出: 2
解释: 打印 "aaa"，再打印 "bbb"。

输入: s = "aba"
输出: 2
解释: 先打印 "aaa"，再打印 "b"（覆盖中间位置）。

输入: s = "abba"
输出: 2
解释: 先打印 "aa"（覆盖位置 0 和 3），再打印 "bb"（覆盖位置 1 和 2）。

4.2 状态定义与转移

预处理：连续相同字符可以合并（aab → ab），因为相同字符可以用一次打印覆盖。预处理后字符串中不再有连续重复字符。

状态：dp[i][j] = 打印字符串区间 [i, j] 所需的最少操作次数。

Base Case：dp[i][i] = 1（打印单个字符需要 1 次）。

转移：

不分割（朴素情况）：先打印 s[i]，需要 1 次；再打印区间 [i+1, j]，需要 dp[i+1][j] 次： $d p [i] [j] = d p [i + 1] [j] + 1$
合并利用（有字符相同时）：如果区间内存在 s[k] == s[i]（k > i），那么打印 s[i..k] 时可以”顺带”打印 s[k]（因为两处字符相同，可以用同一次打印覆盖），所以打印 [k, j] 不需要额外打印 s[k]，等价于 dp[k+1][j]（如果 k < j）或 0（如果 k == j）：

如果 s[k] == s[i]（ $i < k \leq j$ ），则： $d p [i] [j] = min (d p [i] [j], d p [i] [k - 1] + d p [k] [j])$

这里把 [i, j] 分成 [i, k-1] 和 [k, j] 两段，而 [k, j] 中的 s[k] 可以和 s[i] 同时打印（合并为同一次操作），因此 [k, j] 的最少操作数相当于 dp[k+1][j]（s[k] 被免费处理）。

等价写法：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) 其中 s[k] == s[i]，因为 s[k] 和 s[i] 在同一次打印中被处理，dp[i][k] 计算时已经把 s[i..k] 的相同字符纳入了。

更清晰的推导：

dp[i][j] 的初始值 = 1 + dp[i+1][j]（先打印 s[i]，再处理剩余部分）

优化：如果 s[k] == s[i]（i < k <= j），
     打印 s[i] 的那次操作可以"延伸"覆盖到位置 k，
     使得区间 [i, k] 的 s[k] 不需要额外操作。
     即：dp[i][k] 中，s[k] 被 s[i] 那次打印"带到"了 k 位置，
     所以 dp[i][k] = dp[i+1][k-1] + 1（中间 [i+1, k-1] 单独处理，s[i] 和 s[k] 合并为 1 次）
     
     更简单理解：if s[i] == s[k]:
         dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k][j])
         （处理 [i, k-1] + 处理 [k, j]，其中 s[k] 在处理 [i, k-1] 的最后一次打印时顺带完成）

4.3 实现

public int strangePrinter(String s) {
    // 预处理：去掉连续重复字符
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if (i == 0 || s.charAt(i) != s.charAt(i - 1)) {
            sb.append(s.charAt(i));
        }
    }
    s = sb.toString();
    int n = s.length();
 
    int[][] dp = new int[n][n];
 
    // Base case：单个字符
    for (int i = 0; i < n; i++) dp[i][i] = 1;
 
    // 枚举区间长度
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            // 朴素情况：先打印 s[i]，再处理 [i+1, j]
            dp[i][j] = 1 + dp[i + 1][j];
 
            // 优化：如果区间内有 s[k] == s[i]，可以合并操作
            for (int k = i + 1; k <= j; k++) {
                if (s.charAt(k) == s.charAt(i)) {
                    // s[i] 和 s[k] 合并为同一次打印
                    // [i+1, k-1] 独立处理（dp[i+1][k-1]，若空则为 0）
                    // [k, j] 独立处理（但 s[k] 已被免费打印，等价于 dp[k+1][j]）
                    // 实际上等价于：dp[i][k-1]（包含 s[i] 和 s[k] 合并）+ dp[k+1][j]
                    int left = (k > i + 1) ? dp[i + 1][k - 1] : 0;
                    dp[i][j] = Math.min(dp[i][j], 1 + left + (k < j ? dp[k + 1][j] : 0));
                }
            }
        }
    }
    return dp[0][n - 1];
}

简化版写法

很多题解使用 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) 当 s[i] == s[k]，这里 dp[i][k] 的含义是”打印 [i, k] 但 s[k] 已被 s[i] 那次操作带走”，其值等于 dp[i+1][k]（等价变换）。实际面试中记住转移的直觉（“同字符合并一次打印”）比死记公式更重要。

第 5 章 LeetCode 132：分割回文串 II

5.1 题目

LeetCode 132 - Palindrome Partitioning II（困难）

给定字符串 s，将 s 分割成若干子串，每个子串都是回文串。返回最少的分割次数。

输入: s = "aab"
输出: 1
解释: "aab" 分割一次 ["aa","b"]，每个子串都是回文串。

输入: s = "a"
输出: 0

输入: s = "ab"
输出: 1

5.2 两步 DP 解法

这道题是”区间 DP（预计算回文）+ 一维 DP（最少分割）“的组合。

第一步：预计算回文子串

isPalin[i][j] = s[i..j] 是否是回文串。

用区间 DP 计算：

isPalin[i][i] = true（单字符）
isPalin[i][i+1] = (s[i] == s[i+1])
isPalin[i][j] = (s[i] == s[j]) && isPalin[i+1][j-1]（两端字符相同，且中间是回文）

第二步：一维 DP 求最少分割次数

cut[i] = 将 s[0..i] 分割为所有子串均为回文串的最少分割次数。

cut[i] = 0，如果 s[0..i] 本身是回文串
否则：cut[i] = min(cut[j-1] + 1)，其中 j <= i 且 s[j..i] 是回文串

public int minCut(String s) {
    int n = s.length();
 
    // 第一步：预计算所有子串是否是回文串
    boolean[][] isPalin = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || isPalin[i + 1][j - 1])) {
                isPalin[i][j] = true;
            }
        }
    }
 
    // 第二步：一维 DP 求最少分割次数
    int[] cut = new int[n];
    for (int i = 0; i < n; i++) {
        if (isPalin[0][i]) {
            cut[i] = 0; // 整个 [0, i] 是回文串，无需分割
        } else {
            cut[i] = i; // 最差情况：每个字符单独作为回文串
            for (int j = 1; j <= i; j++) {
                if (isPalin[j][i]) {
                    cut[i] = Math.min(cut[i], cut[j - 1] + 1);
                }
            }
        }
    }
    return cut[n - 1];
}

时间复杂度： $O (n^{2})$ （预计算 + 一维 DP 均为 $O (n^{2})$ ）。空间复杂度： $O (n^{2})$ 。

复合 DP 思路

LeetCode 132 是”区间 DP + 一维线性 DP”的复合题型。第一步区间 DP 生成元数据（回文信息），第二步线性 DP 利用这些元数据求最优解。这种”先用区间 DP 预计算，再用线性 DP 求解”的模式在面试中较为常见。

第 6 章区间 DP 的常见变体与延伸

6.1 石子合并（经典区间 DP）

问题：将 n 堆石子合并成一堆，每次只能合并相邻两堆，代价为两堆石子数之和。求最小总代价。

这是矩阵链乘的简化版，直接套区间 DP 模板：

dp[i][j] = min(dp[i][k] + dp[k+1][j]) + sum[i][j]

其中 sum[i][j] 是 [i, j] 的区间和（前缀和预计算）。

6.2 戳气球的双向扩展：插入操作

一些题目是”逆向的戳气球”——不是消除元素，而是插入元素，每次插入在两个已有元素之间，代价与两端元素相关。建模方式与戳气球类似，只是方向相反。

6.3 记忆化搜索的等价写法

区间 DP 也可以用递归 + 记忆化搜索实现，有些人觉得更直观：

int[][] memo;
 
public int solve(int[] arr, int i, int j) {
    if (i >= j) return 0;
    if (memo[i][j] != -1) return memo[i][j];
 
    memo[i][j] = Integer.MAX_VALUE;
    for (int k = i; k < j; k++) {
        memo[i][j] = Math.min(memo[i][j],
            solve(arr, i, k) + solve(arr, k + 1, j) + cost(i, k, j));
    }
    return memo[i][j];
}

递归写法与迭代写法的本质相同，只是遍历顺序由递归调用栈决定（隐式的从小区间到大区间）。

第 7 章区间 DP 题目难点汇总

7.1 区间的边界定义（开区间 vs 闭区间）

戳气球使用开区间 (i, j) 作为状态，不含端点的哨兵气球。石子合并、矩阵链乘使用闭区间 [i, j]。做题时需要注意边界的定义，特别是 k 的枚举范围：

区间类型	k 的范围	分割后的子区间
闭区间 `[i, j]`	`k in [i, j-1]`	`[i, k]` 和 `[k+1, j]`
开区间 `(i, j)`	`k in (i, j)` 即 `k in [i+1, j-1]`	`(i, k)` 和 `(k, j)`

7.2 初始化值的选择

求最小值：初始化为 Integer.MAX_VALUE（注意相加时防止溢出）
求最大值：初始化为 Integer.MIN_VALUE 或 0（根据硬币/代价是否为正）
求计数：初始化为 0（多种方案累加）

7.3 长度为 1 vs 长度为 2 的 base case

单个元素（dp[i][i]）：通常是 0 或 1，按题意而定
相邻两个元素（dp[i][i+1]）：有时需要单独处理（如回文串判断中 isPalin[i][i+1]）
外层循环从 len = 2 还是 len = 1 开始：取决于 dp[i][i] 是否需要单独初始化

小结

区间 DP 的核心在于三个要素：

状态是区间：dp[i][j] 表示对区间 [i, j] 进行操作的最优结果
枚举分割点 k：将大区间分解为两个子区间，子问题相互独立
遍历顺序是「从短到长」：外层枚举区间长度，内层枚举起点，保证计算 dp[i][j] 时所有子区间已就绪

本文涵盖的三道典型题：

题目	核心技巧	难点
矩阵链乘（教材经典）	区间 DP 基础框架	无（纯模板）
LeetCode 312 戳气球	逆向思维：枚举「最后一个」	子问题独立性证明
LeetCode 664 奇怪打印机	同字符合并操作	转移方程的推导
LeetCode 132 回文分割 II	区间 DP 预计算 + 线性 DP	两步 DP 的衔接

下一篇字符串DP进阶：回文子串、正则与通配符匹配将深入字符串 DP 的另一个维度——正则表达式和通配符匹配，这是将”状态机思维”融入 DP 的典型场景。

汀的知识碎片

文章导航

07 区间DP：戳气球、矩阵链乘与「从小区间到大区间」

区间 DP：戳气球、矩阵链乘与「从小区间到大区间」

摘要

第 1 章区间 DP 的核心框架

1.1 什么是区间 DP

1.2 遍历顺序：为什么要按区间长度枚举

1.3 区间 DP 的模板代码

第 2 章矩阵链乘：区间 DP 的经典引入

2.1 问题描述

2.2 区间 DP 建模

第 3 章 LeetCode 312：戳气球

3.1 题目

3.2 正向思考为什么失败

3.3 反向思维：「最后一个被戳破的气球」

3.4 在两端加哨兵

3.5 建模技巧总结

第 4 章 LeetCode 664：奇怪的打印机

4.1 题目

4.2 状态定义与转移

4.3 实现

第 5 章 LeetCode 132：分割回文串 II

5.1 题目

5.2 两步 DP 解法

第 6 章区间 DP 的常见变体与延伸

6.1 石子合并（经典区间 DP）

6.2 戳气球的双向扩展：插入操作

6.3 记忆化搜索的等价写法

第 7 章区间 DP 题目难点汇总

7.1 区间的边界定义（开区间 vs 闭区间）

7.2 初始化值的选择

7.3 长度为 1 vs 长度为 2 的 base case

小结

On this page

汀的知识碎片

文章导航

07 区间DP：戳气球、矩阵链乘与「从小区间到大区间」

区间 DP：戳气球、矩阵链乘与「从小区间到大区间」

摘要

第 1 章 区间 DP 的核心框架

1.1 什么是区间 DP

1.2 遍历顺序：为什么要按区间长度枚举

1.3 区间 DP 的模板代码

第 2 章 矩阵链乘：区间 DP 的经典引入

2.1 问题描述

2.2 区间 DP 建模

第 3 章 LeetCode 312：戳气球

3.1 题目

3.2 正向思考为什么失败

3.3 反向思维：「最后一个被戳破的气球」

3.4 在两端加哨兵

3.5 建模技巧总结

第 4 章 LeetCode 664：奇怪的打印机

4.1 题目

4.2 状态定义与转移

4.3 实现

第 5 章 LeetCode 132：分割回文串 II

5.1 题目

5.2 两步 DP 解法

第 6 章 区间 DP 的常见变体与延伸

6.1 石子合并（经典区间 DP）

6.2 戳气球的双向扩展：插入操作

6.3 记忆化搜索的等价写法

第 7 章 区间 DP 题目难点汇总

7.1 区间的边界定义（开区间 vs 闭区间）

7.2 初始化值的选择

7.3 长度为 1 vs 长度为 2 的 base case

小结

On this page

第 1 章区间 DP 的核心框架

第 2 章矩阵链乘：区间 DP 的经典引入

第 6 章区间 DP 的常见变体与延伸

第 7 章区间 DP 题目难点汇总