数据结构与算法 / 系统课时

按区间长度组织状态计算

按区间长度组织状态计算

区间 DP 最容易写错的往往不是转移式,而是计算顺序:某个大区间依赖更短的子区间时,必须先把这些依赖算完。本文用左右端点建模,并通过最长回文子序列示例掌握区间长度、端点范围和初始化之间的关系。

学习目标

  • 能用 dp[l][r] 表示闭区间状态,并根据区间长度确定合法端点。
  • 能解释为什么区间 DP 通常按长度从短到长计算。
  • 能处理长度为 1、长度为 2 和空输入等常见边界。

用左右端点表达区间

区间 DP 通常把状态定义成“某个连续区间上的最优答案”。例如字符串 s 的最长回文子序列可以定义为:dp[l][r] 表示闭区间 [l, r] 内的最长回文子序列长度。

当 l == r 时,区间里只有一个字符,答案一定是 1,因此长度为 1 的区间是天然的初始化层。更长区间再由更短区间推出,这正是后续计算顺序的依据。

为什么要按长度递增

最长回文子序列的转移只依赖更短的区间:若两端字符相同,就查看 [l+1, r-1];若不同,就比较 [l+1, r] 和 [l, r-1]。所以在计算长度为 len 的区间前,长度小于 len 的状态必须已经得到。

区间 DP 按长度递增填表

如果直接按 l 从小到大、r 从小到大填表,某些依赖可能尚未计算。按长度递增则天然形成拓扑顺序:所有转移都从已完成的短区间流向更长区间。

从长度换算左右端点

设数组或字符串长度为 n,当前区间长度为 length。左端点 l 的最大值是 n - length,右端点由下面的关系得到:

r=l+length−1r = l + length - 1

因此长度循环通常写成 2..n,左端点写成 0..n-length。这里最常见的错误是把右端点写成 l + length,导致越界或把区间实际长度扩大 1。

长度为 2 时还要特别注意 [l+1, r-1] 已经没有元素。可以单独处理,也可以设计带哨兵的状态;对初学实现而言,显式判断最清楚。

主示例:最长回文子序列

下面的 Python 程序完整实现按区间长度递增的计算顺序。输入 bbbab 时,最长回文子序列可以取 bbbb。

python
def longest_palindrome_subseq(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0

    dp = [[0] * n for _ in range(n)]

    # 长度为 1 的区间已经是回文。
    for i in range(n):
        dp[i][i] = 1

    for length in range(2, n + 1):
        for l in range(0, n - length + 1):
            r = l + length - 1

            if s[l] == s[r]:
                # 长度为 2 时,中间区间为空,答案直接是 2。
                dp[l][r] = 2 if length == 2 else dp[l + 1][r - 1] + 2
            else:
                dp[l][r] = max(dp[l + 1][r], dp[l][r - 1])

    return dp[0][n - 1]

if __name__ == "__main__":
    print(longest_palindrome_subseq("bbbab"))

预期输出

text
4

这个示例的关键不是回文问题本身,而是循环骨架:先枚举 length,再枚举 l,最后计算 r。只要当前转移依赖严格更短的区间,这种顺序通常都能保证依赖已就绪。

边界检查与复杂度

实现区间 DP 时,可以先检查三个边界:长度为 1 是否已初始化,长度为 2 是否会访问空区间,以及 r 是否始终小于 n。这三处通常能发现大多数下标错误。

该实现共有约 n2/2n^2/2 个区间,每个区间只做常数次转移,因此时间复杂度是 O(n2)O(n^2),空间复杂度也是 O(n2)O(n^2)。当问题的每个区间还要枚举分割点时,单个状态不再是常数转移,整体复杂度通常会上升到 O(n3)O(n^3)。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

按区间长度组织状态计算

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通