第 27 站 · 动态规划

回文与区间状态

区间 DP：左端点倒序枚举 O(n²)

周赛难度分难度分 1787–难度分 2130· 中位难度分 1959（2/7 道题有 zerotrac 周赛分）

打开 500 路题单 · 第 27 站 · 7 题

先学: 字符串动规
学完去: 没有后续站依赖它。
面试频次: 5 家公司考过 · 面经出现 5 次InterSystems 1、JPMorgan Chase 1、Meta 1、Reevo 1、TikTok / ByteDance 1

先做这道

LC 5最长回文子串中等

卡住再看

比较中心扩展和区间DP，处理奇偶中心并返回原串中的最长片段。

要点

dp[i][j] 只依赖更短的区间 dp[i+1][*] 和 dp[*][j-1]，所以 i 倒序、j 正序填表。
两端字符相等就向内收缩并加 2，否则去掉一端，取两种情况的较大值。
只问回文子串（必须连续）时，中心扩展法 O(n²) 时间、O(1) 空间，更简单。

易错点

i 正序枚举时 dp[i+1][*] 还没有算出来，结果全错。
子序列（可以不连续）和子串（必须连续）是两道题，转移不能混用。
中心扩展要同时试奇数中心 (i, i) 和偶数中心 (i, i+1)。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

区间 DP · 最长回文子序列

「agbdba」的最长回文子序列有多长？

换个输入

·0,0

·0,1

·0,2

·0,3

·0,4

·0,5

·1,1

·1,2

·1,3

·1,4

·1,5

·2,2

·2,3

·2,4

·2,5

·3,3

·3,4

·3,5

·4,4

·4,5

·5,5

当前处理已发现 / 已计算答案

区间长度: —
最长回文子序列: —

dp[i][j] 是「agbdba」第 i 到第 j 个字符里最长回文子序列的长度。它依赖更短的区间，所以按区间长度从短到长填。

速度

步骤 1 / 18

始终成立算长度为 L 的区间时，所有更短的区间都已填好：两端相同就 +2，不同就去掉一端。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 5。

Python

def longest_pal_subseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]  # dp[i][j]: answer for s[i..j]
    for i in range(n - 1, -1, -1):  # i backwards so dp[i+1][*] is ready
        dp[i][i] = 1
        for j in range(i + 1, n):
            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] if n else 0

C++

int longestPalSubseq(const string& s) {
    int n = s.size();
    if (n == 0) return 0;
    vector<vector<int>> dp(n, vector<int>(n, 0));  // dp[i][j]: answer for s[i..j]
    for (int i = n - 1; i >= 0; i--) {  // i backwards so dp[i+1][*] is ready
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++)
            dp[i][j] = s[i] == s[j] ? dp[i + 1][j - 1] + 2 : max(dp[i + 1][j], dp[i][j - 1]);
    }
    return dp[0][n - 1];
}

Java

class Solution {
    int longestPalSubseq(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int[][] dp = new int[n][n]; // dp[i][j]: answer for s[i..j]
        for (int i = n - 1; i >= 0; i--) { // i backwards so dp[i+1][*] is ready
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++)
                dp[i][j] = s.charAt(i) == s.charAt(j)
                        ? dp[i + 1][j - 1] + 2
                        : Math.max(dp[i + 1][j], dp[i][j - 1]);
        }
        return dp[0][n - 1];
    }
}

func longestPalSubseq(s string) int {
	n := len(s)
	if n == 0 {
		return 0
	}
	dp := make([][]int, n) // dp[i][j]: answer for s[i..j]
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for i := n - 1; i >= 0; i-- { // i backwards so dp[i+1][*] is ready
		dp[i][i] = 1
		for j := i + 1; j < n; j++ {
			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]
}

常见变体

这一站的题还会用到下面 2 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

中心扩展：2n − 1 个中心时间 O(n²) · 空间 O(1)

只关心回文「子串」（连续的）时，不必开 n² 的表：每个字母和每个字母之间的空隙都当一次中心，向两边扩到不相等为止，O(n²) 时间、O(1) 空间。LC 5 最长回文子串、LC 647 回文子串计数都这样写；子序列（不连续）才需要区间 DP。

Python

def longest_palindrome(s: str) -> str:
    """Longest palindromic substring, expanding around all 2n - 1 centres (LC 5)."""
    start = end = 0  # the best so far is s[start:end]
    for center in range(2 * len(s) - 1):
        lo, hi = center // 2, (center + 1) // 2  # even centre: a letter; odd: the gap after it
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo, hi = lo - 1, hi + 1
        if hi - lo - 1 > end - start:  # the palindrome found is s[lo+1:hi]
            start, end = lo + 1, hi
    return s[start:end]

C++

// Longest palindromic substring, expanding around all 2n - 1 centres (LC 5).
string longestPalindrome(const string& s) {
    int n = s.size(), start = 0, end = 0;  // the best so far is s[start, end)
    for (int center = 0; center < 2 * n - 1; center++) {
        int lo = center / 2, hi = (center + 1) / 2;  // even centre: a letter; odd: the gap after it
        while (lo >= 0 && hi < n && s[lo] == s[hi]) lo--, hi++;
        if (hi - lo - 1 > end - start) start = lo + 1, end = hi;  // the palindrome found is s[lo+1, hi)
    }
    return s.substr(start, end - start);
}

Java

class Solution {
    // Longest palindromic substring, expanding around all 2n - 1 centres (LC 5).
    String longestPalindrome(String s) {
        int n = s.length(), start = 0, end = 0; // the best so far is s[start, end)
        for (int center = 0; center < 2 * n - 1; center++) {
            int lo = center / 2, hi = (center + 1) / 2; // even centre: a letter; odd: the gap after it
            while (lo >= 0 && hi < n && s.charAt(lo) == s.charAt(hi)) {
                lo--;
                hi++;
            }
            if (hi - lo - 1 > end - start) { // the palindrome found is s[lo+1, hi)
                start = lo + 1;
                end = hi;
            }
        }
        return s.substring(start, end);
    }
}

// longestPalindrome returns the longest palindromic substring, expanding around all 2n - 1 centres (LC 5).
func longestPalindrome(s string) string {
	n, start, end := len(s), 0, 0 // the best so far is s[start:end]
	for center := 0; center < 2*n-1; center++ {
		lo, hi := center/2, (center+1)/2 // even centre: a letter; odd: the gap after it
		for lo >= 0 && hi < n && s[lo] == s[hi] {
			lo, hi = lo-1, hi+1
		}
		if hi-lo-1 > end-start { // the palindrome found is s[lo+1:hi]
			start, end = lo+1, hi
		}
	}
	return s[start:end]
}

区间 DP：枚举区间里最后一个处理的元素时间 O(n³) · 空间 O(n²)

操作会改变邻居（戳气球后两边并拢、合并石子）时，枚举「第一个」做不下去，要枚举「最后一个」：k 最后被戳时，它的邻居正好是区间两端 i 和 j，左右两段互不影响。i 倒着走、j 正着走，保证子区间先算好。LC 312 戳气球、LC 1039 多边形三角剖分的最低得分。

Python

def max_coins(nums: list[int]) -> int:
    """Most coins from bursting all balloons (LC 312): pick the last one burst in each range."""
    vals = [1] + nums + [1]
    n = len(vals)
    dp = [[0] * n for _ in range(n)]  # dp[i][j]: best for the balloons strictly between i and j
    for i in range(n - 1, -1, -1):  # i backwards so dp[k][j] with k > i is ready
        for j in range(i + 2, n):
            for k in range(i + 1, j):  # k goes last: its neighbours are then i and j
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + vals[i] * vals[k] * vals[j])
    return dp[0][n - 1]

C++

// Most coins from bursting all balloons (LC 312): pick the last one burst in each range.
int maxCoins(const vector<int>& nums) {
    vector<int> vals{1};
    vals.insert(vals.end(), nums.begin(), nums.end());
    vals.push_back(1);
    int n = vals.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));  // dp[i][j]: best for the balloons strictly between i and j
    for (int i = n - 1; i >= 0; i--)  // i backwards so dp[k][j] with k > i is ready
        for (int j = i + 2; j < n; j++)
            for (int k = i + 1; k < j; k++)  // k goes last: its neighbours are then i and j
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + vals[i] * vals[k] * vals[j]);
    return dp[0][n - 1];
}

Java

class Solution {
    // Most coins from bursting all balloons (LC 312): pick the last one burst in each range.
    int maxCoins(int[] nums) {
        int n = nums.length + 2;
        int[] vals = new int[n];
        vals[0] = vals[n - 1] = 1;
        System.arraycopy(nums, 0, vals, 1, nums.length);
        int[][] dp = new int[n][n]; // dp[i][j]: best for the balloons strictly between i and j
        for (int i = n - 1; i >= 0; i--) // i backwards so dp[k][j] with k > i is ready
            for (int j = i + 2; j < n; j++)
                for (int k = i + 1; k < j; k++) // k goes last: its neighbours are then i and j
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + vals[i] * vals[k] * vals[j]);
        return dp[0][n - 1];
    }
}

// maxCoins returns the most coins from bursting all balloons (LC 312).
func maxCoins(nums []int) int {
	vals := append(append([]int{1}, nums...), 1)
	n := len(vals)
	dp := make([][]int, n) // dp[i][j]: best for the balloons strictly between i and j
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for i := n - 1; i >= 0; i-- { // i backwards so dp[k][j] with k > i is ready
		for j := i + 2; j < n; j++ {
			for k := i + 1; k < j; k++ { // k goes last: its neighbours are then i and j
				dp[i][j] = max(dp[i][j], dp[i][k]+dp[k][j]+vals[i]*vals[k]*vals[j])
			}
		}
	}
	return dp[0][n-1]
}

为什么对

dp[i][j]（s[i..j] 的最长回文子序列）只依赖 dp[i+1][j−1]、dp[i+1][j]、dp[i][j−1]，都是更短的区间，所以 i 从后往前、j 从前往后填，用到时一定已经算好。
两端相等时把两端都用上不会更差：任何最优回文如果没有同时用上这两个字符，可以把它最外层的一对换成这两个字符，长度不变。
中心扩展：每个回文子串都有唯一的中心（一个字符或两个字符之间），一共 2n − 1 个中心，从每个中心向外扩展就枚举了所有回文子串。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文

回文区间 DP，我定义 dp[i][j] 为 s[i..j] 上的答案。两端相等就向内收缩并加 2，否则去掉一端，在两种里取更好的。每个状态只依赖更短的区间，所以 i 从后往前、j 从前往后填表。如果是连续的回文子串，我更常用中心扩展：2n − 1 个中心各自向外扩，O(n²) 时间、O(1) 空间。

English

For palindrome ranges I let dp[i][j] be the answer on s[i..j]. If the two ends match, I move inward and add two; otherwise I drop one end and keep the better result. Every state depends only on shorter ranges, so I fill i backwards and j forwards. For contiguous palindromic substrings I usually expand around each of the 2n − 1 centres instead, which is O(n²) time and O(1) space.

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。只存在这台设备上；登录后会合并到你的账号。

对照要点（0/3）

dp[i][j]（s[i..j] 的最长回文子序列）只依赖 dp[i+1][j−1]、dp[i+1][j]、dp[i][j−1]，都是更短的区间，所以 i 从后往前、j 从前往后填，用到时一定已经算好。
两端相等时把两端都用上不会更差：任何最优回文如果没有同时用上这两个字符，可以把它最外层的一对换成这两个字符，长度不变。
中心扩展：每个回文子串都有唯一的中心（一个字符或两个字符之间），一共 2n − 1 个中心，从每个中心向外扩展就枚举了所有回文子串。

小测

4 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。去 OA 选择题练习

4 道题

用「中心扩展」找回文子串，长度为 n 的字符串一共要从多少个中心向两边扩展？
- n
- n²
- 2n - 1
- n / 2
区间 DP 求最长回文子序列：dp[i][j] 依赖 dp[i+1][j-1]、dp[i+1][j] 和 dp[i][j-1]。下面哪种填表顺序是对的？
- i 从 0 往 n-1，j 从 n-1 往 i
- i 从 n-1 往 0，j 从 i 往 n-1
- i 从 0 往 n-1，j 从 0 往 n-1
- 任何顺序都可以

n = len(s)。最坏情况下的时间和额外空间分别是？

def count_pal(s):
    n, total = len(s), 0
    for c in range(2 * n - 1):
        lo, hi = c // 2, c // 2 + c % 2
        while lo >= 0 and hi < n and s[lo] == s[hi]:
            total += 1
            lo -= 1
            hi += 1
    return total

O(n²) 时间，O(n²) 空间
O(n²) 时间，O(1) 空间
O(n³) 时间，O(1) 空间
O(n) 时间，O(1) 空间

n = len(s)。时间复杂度是？

def count_pal(s):
    n = len(s)
    return sum(s[i:j] == s[i:j][::-1]
               for i in range(n) for j in range(i + 1, n + 1))

O(n³)
O(2^n)
O(n² log n)
O(n²)

作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

分档练习

本站在 500 路里的 7 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

核心 4

#	题目	一句话思路	难度分
5	最长回文子串	比较中心扩展和区间DP，处理奇偶中心并返回原串中的最长片段。
647	回文子串	枚举中心统计按位置区分的回文，明确子串计数并不按文本去重。
516	最长回文子序列	区分子串与子序列，在左右端点匹配或跳过的选择中求最优长度。
1312	让字符串成为回文串的最少插入次数	把不匹配端点转为一次插入，并与最长回文子序列建立联系。	难度分 1787

进阶 3

#	题目	一句话思路	难度分
132	分割回文串 II	预处理回文区间再做最少切分，区分切割次数与分段数量。
1039	多边形三角剖分的最低得分	固定多边形一条边，枚举第三个顶点拆成独立区间，是区间划分的直观训练。	难度分 2130
312	戳气球	通过枚举最后戳破的气球稳定相邻边界，训练反向考虑操作顺序。

本站 OA 真题 9

Palindromic SubstringsAmazon
Count Distinct Palindromic SubstringsCitadel
Palindromic SubstringsCitadel
Find Longest Palindromic SubstringCisco
Longest Palindromic SubstringCisco
DNA Sequencing — Palindrome Transformation CostIntuit
Palindrome CounterGoldman Sachs
Count Palindromic SubstringsPure Storage
Count Different Palindrome SubstringsPure Storage

全部 9 道