第 59 课 - 区间 DP

学习目标

完成本课后，你将能够：

理解区间动态规划（Interval DP）的基本思想和适用场景。
掌握定义区间DP状态 dp[i][j] 的通用方法。
掌握区间DP状态转移方程的推导与设计，特别是 k 的枚举方式。
能够识别并解决类似“最长回文子序列”、“戳气球”等经典区间DP问题。

核心概念

区间DP，顾名思义，是作用于一个序列（如数组、字符串）的某个连续子区间 [i, j] 上的动态规划。它的核心思想是： 对于一个问题，我们通过枚举其所有可能的子问题（子区间）的解，并将它们组合起来，从而得到原问题的最优解。

想象你在切一根长面包，每切一刀都有成本，最终目的是以最小总成本把它切成一片片。你不能随意乱切，每一步的决策都依赖于之前已经切出的片段长度。区间DP正是描述这种“将大区间不断分解为小区间，并综合小区间解以得到大区间解”的过程。

关键特征：

状态定义： dp[i][j] 通常表示从原序列的索引 i 到 j 这个子区间所能达到的最优解（最大值、最小值、个数等）。
状态转移： 我们需要枚举一个分割点 k（i <= k < j），将区间 [i, j] 分割为 [i, k] 和 [k+1, j] 两个子区间。然后结合两个子区间的解，并考虑跨过这两个子区间的“连接操作”成本或收益，来更新 dp[i][j]。
计算顺序： 由于 dp[i][j] 依赖于更短的子区间，我们通常以区间长度 len 为外层循环，从小到大地计算所有长度为 len 的区间，最终得到整个序列 dp[0][n-1] 的解。

伪代码框架：

# 假设序列长度为 n
n = len(nums)
# 初始化DP表
dp = [[0] * n for _ in range(n)]

# 枚举区间长度 len
for length in range(2, n+1): # 长度从2到n，长度为1的区间通常有边界值
    # 枚举区间起点 i
    for i in range(n - length + 1):
        j = i + length - 1 # 计算区间终点 j
        # 初始化 dp[i][j] 为一个极值（根据问题要求）
        dp[i][j] = float('-inf') # 或 float('inf')
        # 枚举分割点 k
        for k in range(i, j):
            # 状态转移：结合左右子区间的结果
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i, k, j))

代码示例：最长回文子序列

问题描述： 给定一个字符串 s，找到其中最长的回文子序列的长度。 示例： 输入: "bbbab"，输出: 4 (一个可能的最长回文子序列是 "bbbb")

思路：

状态定义： dp[i][j] 表示子串 s[i..j] 中最长回文子序列的长度。
初始状态： 所有长度为1的子串，dp[i][i] = 1。
状态转移：
- 如果 s[i] == s[j]，那么它们可以作为回文的首尾。此时，dp[i][j] = dp[i+1][j-1] + 2。
- 如果 s[i] != s[j]，那么最长回文子序列要么在 s[i..j-1] 中，要么在 s[i+1..j] 中。dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    # 如果字符串为空，长度为0
    if n == 0:
        return 0
    # 创建 DP 表，dp[i][j] 表示 s[i..j] 的最长回文子序列长度
    dp = [[0] * n for _ in range(n)]

    # 初始状态：长度为1的子串，最长回文子序列长度为1
    for i in range(n):
        dp[i][i] = 1

    # 枚举子串长度 len
    for length in range(2, n + 1): # 从2开始，1已经初始化
        # 枚举起始索引 i
        for i in range(n - length + 1):
            j = i + length - 1 # 结束索引
            # 状态转移
            if s[i] == s[j]:
                # 当 i 和 j 相邻时，len=2，dp[i+1][j-1] 为 0，所以结果是2
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                # 不相等时，取去掉左端或右端后的较大值
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])

    # 最终结果：整个字符串 s[0..n-1] 的最长回文子序列长度
    return dp[0][n-1]

# 测试
s = "bbbab"
print(longestPalindromeSubseq(s)) # 输出: 4

实践练习

练习1：回文子串计数（基础）

描述： 给定一个字符串 s，请计算其中回文子串的数量。 示例： 输入: "aaa"，输出: 6 (所有子串："a", "a", "a", "aa", "aa", "aaa" 都是回文) 提示： 修改上面最长回文子序列的代码，将状态 dp[i][j] 定义为一个布尔值，表示 s[i..j] 是否是回文，并进行计数。

练习2：戳气球（经典）

描述： 有 n 个气球，编号为 0 到 n-1，每个气球上都标有一个数字。当你戳破气球 i 时，你会获得 nums[left] * nums[i] * nums[right] 个硬币，其中 left 和 right 是相邻气球的索戳破 i 后，left 和 right 变为相邻。找出戳破所有气球能获得的最大硬币数。 示例： 输入: [3,1,5,8]，输出: 167 提示： 这是一个经典的逆向思维区间DP。定义 dp[i][j] 为戳破开区间 (i, j) 内所有气球能获得的最大硬币数（开区间，不包括 i 和 j）。枚举最后一个被戳破的气球 k。

练习3：多边形三角剖分的最低得分（进阶）

描述： 给定一个凸 n 边形，每个顶点有一个权重。将多边形用不相交的对角线划分为若干个三角形，每个三角形的得分为三个顶点权重的乘积。求所有可能三角剖分中，所有三角形得分之和的最小值。 示例： 输入: weights = [1,2,3]，表示一个三角形，输出: 6 提示： 定义 dp[i][j] 为从顶点 i 到顶点 j 构成的多边形子部分的最小剖分得分。枚举中间顶点 k（i < k < j），将多边形 (i, k, j) 这个三角形分割出来。

常见错误

初始化不正确： 忘记初始化长度为1或0的区间（dp[i][i] 或 dp[i][i-1]），这会导致状态转移时使用未定义的值。
循环顺序错误： 区间DP的正确循环顺序是 长度 -> 起点 -> 分割点。错误地先枚举起点再枚举长度，会导致计算 dp[i][j] 时，其依赖的子区间 dp[i][k] 或 dp[k+1][j] 可能还未被计算。
边界条件处理不当： 在转移方程中，当 i+1 > j-1 时（例如长度为2的区间），需要特别处理，避免数组越界。
将问题错误建模： 并非所有序列上的DP都是区间DP。区间DP的显著特征是需要通过枚举一个“分割点”来组合两个相邻子区间的解。

小结

区间DP适用于求解序列上某个连续子区间的最优解问题，其解可以通过组合更小子区间的解得到。
核心状态定义为 dp[i][j]，表示原序列索引 i 到 j 这个区间的解。
状态转移的核心在于枚举分割点 k，将大区间 [i, j] 拆分为两个小子区间 [i, k] 和 [k+1, j]。
计算顺序通常以区间长度 len 从小到大进行，确保计算大区间时，所需的小区间结果已经就绪。
经典问题包括最长回文子序列、戳气球、矩阵链乘法、石子合并等，识别这些问题的“区间合并”特征是关键。

下一课预告： 我们将学习动态规划的另一大分支——树形 DP，它将动态规划应用于树结构上，解决子树相关的最优问题。

练习编辑器

rust