30 秒速览

  • 区间 DP：状态定义在区间 [i, j] 上
  • 遍历顺序：按区间长度从小到大
  • 回文 DP：dp[i][j] = s[i:j+1] 是否是回文
  • 典型问题：最长回文子串、回文子串计数、矩阵链乘法

一、直觉建立

什么是区间 DP？

普通线性 DP 的状态是 dp[i]，表示位置 i 的状态。 区间 DP 的状态是 dp[i][j]，表示区间 [i, j] 的状态。

普通 DP:    dp[0], dp[1], dp[2], ...
区间 DP:    dp[0][0], dp[0][1], dp[0][2], ...
            dp[1][1], dp[1][2], dp[1][3], ...
            ...

遍历顺序的关键

区间 DP 必须按区间长度递增遍历，因为大区间依赖小区间。

for length in range(1, n + 1):       # 区间长度
    for i in range(n - length + 1):  # 左端点
        j = i + length - 1           # 右端点
        # 计算 dp[i][j]

二、回文问题

回文的性质

如果 s[i] == s[j] 且 s[i+1:j] 是回文，则 s[i:j+1] 是回文

这提示我们可以用 DP 来判断回文。

dp 定义

dp[i][j] = s[i:j+1] 是否是回文

转移方程

if s[i] == s[j]:
    dp[i][j] = dp[i+1][j-1]  # 首尾相同，看中间
else:
    dp[i][j] = False

特殊情况：

  • 长度为 1：dp[i][i] = True（单个字符是回文）
  • 长度为 2：dp[i][i+1] = (s[i] == s[i+1])

三、典型例题

例题 1：LC 5. 最长回文子串

题目：给定字符串 s，找到最长回文子串。

方法一：DP

def longestPalindrome(s: str) -> str:
    n = len(s)
    if n <= 1:
        return s

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

    # 初始化：单个字符是回文
    for i in range(n):
        dp[i][i] = True

    start, max_len = 0, 1

    # 按长度遍历
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            if s[i] == s[j]:
                if length == 2:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i+1][j-1]

                if dp[i][j] and length > max_len:
                    start = i
                    max_len = length

    return s[start:start + max_len]

复杂度：时间 O(n²)，空间 O(n²)

方法二：中心扩展（更优）

def longestPalindrome(s: str) -> str:
    if not s:
        return ""

    def expand(left: int, right: int) -> str:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    result = s[0]
    for i in range(len(s)):
        # 奇数长度
        odd = expand(i, i)
        # 偶数长度
        even = expand(i, i + 1)

        if len(odd) > len(result):
            result = odd
        if len(even) > len(result):
            result = even

    return result

复杂度：时间 O(n²)，空间 O(1)

例题 2：LC 647. 回文子串

题目：计算字符串中回文子串的个数。

示例：

输入：s = "abc"
输出：3（"a", "b", "c"）

输入：s = "aaa"
输出：6（"a", "a", "a", "aa", "aa", "aaa"）

方法一：DP

def countSubstrings(s: str) -> int:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0

    for i in range(n):
        dp[i][i] = True
        count += 1

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            if s[i] == s[j]:
                if length == 2:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i+1][j-1]

                if dp[i][j]:
                    count += 1

    return count

方法二：中心扩展

def countSubstrings(s: str) -> int:
    count = 0

    def expand(left: int, right: int) -> int:
        cnt = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            cnt += 1
            left -= 1
            right += 1
        return cnt

    for i in range(len(s)):
        # 以 i 为中心的奇数长度回文
        count += expand(i, i)
        # 以 i,i+1 为中心的偶数长度回文
        count += expand(i, i + 1)

    return count

复杂度：时间 O(n²)，空间 O(1)

例题 3：LC 131. 分割回文串

题目：给定字符串 s，将 s 分割成一些子串，使每个子串都是回文。返回所有可能的分割方案。

示例：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

思路

回溯 + 预处理回文表。

def partition(s: str) -> list[list[str]]:
    n = len(s)

    # 预处理：is_pal[i][j] = s[i:j+1] 是否是回文
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2:
                    is_pal[i][j] = True
                else:
                    is_pal[i][j] = is_pal[i+1][j-1]

    result = []
    path = []

    def backtrack(start):
        if start == n:
            result.append(path[:])
            return

        for end in range(start, n):
            if is_pal[start][end]:
                path.append(s[start:end+1])
                backtrack(end + 1)
                path.pop()

    backtrack(0)
    return result

复杂度：时间 O(n × 2^n)，空间 O(n²)

例题 4：LC 132. 分割回文串 II

题目：返回将 s 分割成回文子串的最小切割次数。

思路

DP + 预处理。

def minCut(s: str) -> int:
    n = len(s)

    # 预处理回文表
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2:
                    is_pal[i][j] = True
                else:
                    is_pal[i][j] = is_pal[i+1][j-1]

    # dp[i] = s[0:i+1] 的最小切割次数
    dp = [0] * n

    for i in range(n):
        if is_pal[0][i]:
            dp[i] = 0  # 整个是回文，不需要切割
        else:
            dp[i] = i  # 最坏情况：每个字符切一次
            for j in range(i):
                if is_pal[j+1][i]:
                    dp[i] = min(dp[i], dp[j] + 1)

    return dp[n-1]

复杂度：时间 O(n²)，空间 O(n²)

例题 5：LC 516. 最长回文子序列

题目：给定字符串 s，找到最长回文子序列的长度。

思路

子序列可以不连续，用区间 DP。

dp[i][j] = s[i:j+1] 的最长回文子序列长度

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    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 i in range(n - length + 1):
            j = i + length - 1

            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])

    return dp[0][n-1]

复杂度：时间 O(n²)，空间 O(n²)

四、区间 DP 进阶

例题 6：LC 312. 戳气球

题目：有 n 个气球，戳破气球 i 可以得到 nums[i-1] * nums[i] * nums[i+1] 个金币。求最大金币数。

思路

逆向思考：不是戳破，而是添加气球。

dp[i][j] = 在开区间 (i, j) 内戳破所有气球能得到的最大金币数

def maxCoins(nums: list[int]) -> int:
    # 添加边界
    nums = [1] + nums + [1]
    n = len(nums)

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

    # 按区间长度遍历
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            # k 是最后被戳破的气球
            for k in range(i + 1, j):
                dp[i][j] = max(
                    dp[i][j],
                    dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]
                )

    return dp[0][n-1]

复杂度：时间 O(n³)，空间 O(n²)

例题 7：LC 1039. 多边形三角剖分的最低得分

题目：给定凸多边形顶点值，将多边形剖分成三角形，使得分最低。

思路

区间 DP：dp[i][j] = 从顶点 i 到 j 的最低得分

def minScoreTriangulation(values: list[int]) -> int:
    n = len(values)
    dp = [[0] * n for _ in range(n)]

    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')

            for k in range(i + 1, j):
                dp[i][j] = min(
                    dp[i][j],
                    dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]
                )

    return dp[0][n-1]

五、区间 DP 模板

基本模板

def interval_dp(s):
    n = len(s)
    dp = [[初始值] * n for _ in range(n)]

    # 初始化：长度为 1 的区间
    for i in range(n):
        dp[i][i] = ...

    # 按区间长度遍历
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # 状态转移
            dp[i][j] = ...

    return dp[0][n-1]

分割点模板

for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        for k in range(i, j):  # 枚举分割点
            dp[i][j] = combine(dp[i][k], dp[k+1][j])

六、常见错误与陷阱

错误 1：遍历顺序错误

# 错误：按 i 递增遍历
for i in range(n):
    for j in range(i + 1, n):
        # dp[i+1][j-1] 可能还没计算！

# 正确：按区间长度遍历
for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1

错误 2：边界初始化遗漏

# 忘记初始化单字符
for i in range(n):
    dp[i][i] = True  # 必须初始化

错误 3：回文判断的长度 2 特判

# 长度为 2 时，dp[i+1][j-1] = dp[i+1][i] 是无效的
if length == 2:
    dp[i][j] = (s[i] == s[j])
else:
    dp[i][j] = dp[i+1][j-1] and (s[i] == s[j])

七、复盘清单

触发信号

  • 回文相关问题
  • 区间合并/分割
  • 矩阵链/三角形剖分
  • 状态依赖小区间

算法选择

  • 回文子串 → 中心扩展或 DP
  • 回文子序列 → 区间 DP
  • 区间合并 → 区间 DP + 枚举分割点

实现检查

  • 按区间长度遍历
  • 边界初始化
  • 长度 2 特判
  • 下标不越界

八、题目清单

回文问题

题号题目难度考点
5最长回文子串Medium中心扩展/DP
647回文子串Medium中心扩展
516最长回文子序列Medium区间 DP
131分割回文串Medium回溯+DP
132分割回文串 IIHardDP

区间 DP

题号题目难度考点
312戳气球Hard区间 DP
1039多边形三角剖分Medium区间 DP
375猜数字大小 IIMedium区间 DP
1000合并石堆Hard区间 DP