企业官网建设流程全解析

1. 回文这一类题，为什么绕不开区间DP这条主线

算法训练营走到第56天，动态规划这一模块已经进入收尾阶段，剩下的两道题一个叫回文子串，一个叫最长回文子序列。很多人第一次看到这两题会本能地往"字符串匹配"或者"中心扩展"上想，这没错，但训练营把它们放在动态规划章节的最后，用意其实很明确：回文问题的天然结构就是区间，而区间就是二维DP最典型的应用场地。

先把这两道题的核心差别摆在最前面，因为它决定了你后面所有代码的骨架。回文子串要求连续，s[i..j]必须是原串里切下来的一段，中间不能跳过字符；最长回文子序列不要求连续，允许从原串里挑着取字符，只要挑出来的顺序不变、读起来正反一样就行。这个差别听起来只是"连续"两个字，落到代码上是截然不同的两种转移方式：前者一旦s[i] != s[j]就直接判死，后者却还能靠"砍掉左端"或"砍掉右端"继续抢救。

我见过不少人在这一天上完课之后，回头做第5题"最长回文子串"还是会卡住，原因往往不是不会写递推式，而是不知道二维表格该按什么顺序填。回文类DP最反直觉的地方就在这里：大多数线性DP你是从前往后推的，dp[i]依赖dp[i-1]；但回文DP里dp[i][j]依赖的是dp[i+1][j-1]，也就是它左下方那个格子。这意味着如果你按常规的i从小到大去推，你需要的那个值根本还没算出来。

这一节我想先把"为什么非得是区间"这件事讲透。字符串上的回文判断有一个非常朴素的性质：一个大区间是不是回文，只取决于它两端字符是否相等，以及去掉两端之后的小区间是不是回文。这个性质是递归的、自相似的，正好是动态规划最喜欢的形状。你可以把它想象成剥洋葱，一层一层往里剥，最里面剩一个字符或者两个相同字符的时候，整颗洋葱就成立了。

一旦接受了这个"剥洋葱"的模型，状态定义几乎是自动浮现的：dp[i][j]描述区间[i, j]的某种回文性质。区别只在于这个"性质"是什么——在回文子串里它是布尔值（是不是回文），在最长回文子序列里它是长度（最长能有多长）。同一个区间模型，换一个状态含义，就是两道完全不同难度的题，这也是动态规划最迷人的地方，也是最能拉开水平差距的地方。

1.1 从中心扩展说起：暴力思路的天花板在哪里

在正式进入DP之前，值得花点时间把中心扩展法捋一遍，因为它是理解回文结构最好的入口，而且在实际工程里往往比DP更实用。

中心扩展的思路极其直白：回文串一定有一个"中心"，这个中心要么是某个字符（奇数长度），要么是两个相邻字符之间的缝隙（偶数长度）。于是我们枚举所有可能的中心，从中心向两边同时走，只要两边字符相等就继续扩，一旦不等就停。全串一共有2n - 1个中心（n个字符中心 + n-1个缝隙中心），每个中心最多扩 n/2 步，总复杂度 O(n²)，空间 O(1)。

public int countSubstrings(String s) { int n = s.length(), ans = 0; for (int center = 0; center < 2 * n - 1; center++) { int l = center / 2; int r = l + center % 2; while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) { ans++; l--; r++; } } return ans; }

这段代码只有十行，却把"回文子串"这道题解决了，而且空间是常数级。那为什么训练营还要专门讲DP版本？因为中心扩展只能回答"有多少个回文子串"这类计数问题，它没法复用中间结果去回答更复杂的问题。比如"把字符串切分成若干回文子串，最少切几刀"（第132题），你就需要提前知道任意一个区间[i, j]是不是回文，这时候一张预处理的布尔表就是刚需，而中心扩展法虽然也能顺手填这张表，但填表逻辑和DP版本本质上是同一件事。

所以我的建议是：中心扩展当作理解工具和面试备用方案，二维DP表当作必须掌握的基本功。两者都写一遍，你对回文结构的理解会上一个台阶。

1.2 状态是区间，那遍历顺序就被锁死了

前面说到dp[i][j]依赖dp[i+1][j-1]，这个依赖关系直接决定了填表方向。我在纸上画过很多次这张表，横轴是j，纵轴是i，有效的格子只在右上半三角（因为i <= j）。dp[i][j]的左下方是dp[i+1][j-1]，正下方是dp[i+1][j]，正左方是dp[i][j-1]。

看清楚了这三个邻居的位置，遍历顺序就没有任何悬念了：必须保证算dp[i][j]的时候，它的下方、左方、左下方都已经算完。满足这个条件的方式有两种，一种是i从大到小、j从小到大；另一种是按区间长度len从小到大枚举。这两种写法在数学上等价，但在代码可读性和出错概率上差别很大。

我个人的偏好是按区间长度枚举，因为它的语义最清晰："我先算出所有长度为1的区间，再算长度为2的，再算长度为3的……"这跟剥洋葱的顺序完全一致，写起来不容易晕。但训练营里更常见的是i倒序遍历，因为它少一层循环，代码更短。两种我都会在后面给出完整写法。

提示：写区间DP的时候，先在纸上画出那张上三角表，把dp[i][j]的三个依赖方向标出来，再决定循环怎么写。这一步花两分钟，能省掉半小时的调试。

2. 回文子串：布尔状态表的填表方向最容易翻车

第647题"回文子串"要求统计字符串里所有回文子串的个数，位置不同的相同内容算不同子串。这道题是回文DP的入门题，状态定义简单到几乎不用思考，但恰恰因为简单，很多人在遍历顺序上栽跟头。

状态定义：dp[i][j]表示区间s[i..j]是否为回文串，类型是boolean。这里有个细节值得说：Java里boolean数组默认全是false，这对本题恰好是"安全的默认值"，因为未计算过的格子本来就该当作"不是回文"。但如果换成int数组、默认值是0，而你的合法答案里也包含0，那就麻烦了，必须显式初始化。默认值刚好等于"无效状态"是一种运气，不能当成习惯，这是我在踩过几次坑之后才真正养成的意识。

2.1 递推式其实只有一句话

s[i]和s[j]相等还是不相等，这是唯一的分叉点。

不相等的时候，[i, j]这个区间绝对不可能是回文，因为两端都对不上，直接false。相等的时候要看里面：如果j - i <= 1，说明这个区间长度是1或者2，两端相等就已经是回文了，直接true；否则就要看dp[i+1][j-1]。

public int countSubstrings(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; int ans = 0; for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { if (j - i <= 1) { dp[i][j] = true; } else { dp[i][j] = dp[i + 1][j - 1]; } } if (dp[i][j]) ans++; } } return ans; }

注意j的起点是i而不是i+1，因为长度为1的区间本身也是回文，dp[i][i]必须被算到。这一点如果漏了，答案会少 n 个，而且测试用例里如果全是单字符你才会发现，很容易漏掉。

if (j - i <= 1)这个判断涵盖了长度1和长度2两种情况，写成j - i <= 1比写成两个分支更紧凑。有些人喜欢把它拆成if (j == i) true; else if (j == i + 1) true;，逻辑一样但代码更长，没必要。

2.2 倒序i的循环为什么不能换成正序

这是本篇文章里我最想强调的一个点。你把上面代码里的for (int i = n - 1; i >= 0; i--)改成for (int i = 0; i < n; i++)，代码能编译、能跑、不会崩，但在大多数用例上结果是错的。为什么？因为dp[i][j]依赖dp[i+1][j-1]，i+1是"下一行"，你正序遍历的时候下一行还没开始填，全是初始值false。

更隐蔽的是，有些用例碰巧能通过。比如"aaa"，因为所有字符都相同，dp[i+1][j-1]依赖的那格即使没算，只要所有字符相等，最终结果也不会差。这种"跑通了几个用例就以为对了"的错觉是最危险的，我在训练营里见过太多人在这种地方翻车。

按区间长度枚举的写法可以彻底规避这个问题，因为它把"依赖关系"显式化了：

public int countSubstrings(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; int ans = 0; for (int len = 1; len <= n; len++) { for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; if (s.charAt(i) == s.charAt(j)) { if (len <= 2) dp[i][j] = true; else dp[i][j] = dp[i + 1][j - 1]; } if (dp[i][j]) ans++; } } return ans; }

从可读性上看，我更推荐这种写法。len从小到大推进的时候，dp[i+1][j-1]对应的区间长度是len - 2，一定已经在上一轮算完了，因果关系一目了然。

2.3 空间压缩在这里基本没意义

很多人学到这一步会习惯性地问："能不能压成一维？"答案是可以，但不建议。

dp[i][j]依赖dp[i+1][j-1]，一维滚动的时候这个值会被覆盖掉，你必须额外用一个变量pre把它存下来。技术上完全可行，但代码可读性会下降一大截，而且本题的 n 上限是1000，boolean[n][n]在 Java 里大约占 1MB，完全在限制之内。为了省这点内存把代码写复杂，得不偿失。

空间压缩要判断值不值：当 n 达到 10⁵ 级别、二维数组直接爆内存的时候，压缩是刚需；当 n 只有几百上千的时候，优先保证代码正确和可读。这个判断标准我认为比任何优化技巧都重要。

顺带提一句第5题"最长回文子串"，它跟第647题共享完全相同的状态定义和遍历顺序，区别只在于你要记录的是"最长的那个区间"而不是"区间个数"。会了647，第5题只是多两行代码的事：

if (dp[i][j] && j - i + 1 > maxLen) { maxLen = j - i + 1; start = i; }

真正让第5题独立成题的是 Manacher 算法，它把复杂度压到 O(n)。Manacher 的核心思想是在字符之间插入分隔符，把奇偶长度的情况统一，然后利用回文的对称性跳过重复计算。这个算法我建议先理解原理、知道什么时候该用，但不必强求默写，实际面试中写出中心扩展加解释复杂度已经足够。

3. 最长回文子序列：把回文翻译成"匹配"的思维跳跃

第516题"最长回文子序列"是这一天内容里难度最高的一道，也是最能体现"状态定义决定一切"的一道。它的题面跟647几乎一样，只差"连续"两个字，但转移方程完全是另一套逻辑。

关键在于理解：子序列不连续，意味着即使两端字符对不上，我还留有余地。假设s[i] != s[j]，这个区间的最长回文子序列它一定不包含i和j这两个位置同时作为两端（因为对不上），那它要么来自[i+1, j]，要么来自[i, j-1]，两者取大就行。这个"取大"的动作就是子序列类DP的灵魂，也是它跟子串类DP的分水岭。

状态定义：dp[i][j]表示区间s[i..j]内最长回文子序列的长度。

转移分两支：

初始化：dp[i][i] = 1，因为单个字符本身就是长度1的回文子序列。这里不能靠数组默认值0，必须显式填1，否则所有结果都会偏小。

3.1 长度为1的初始化和长度为2的边界

代码骨架跟647高度相似，但初始化部分要格外小心：

public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int i = 0; i < n; i++) dp[i][i] = 1; for (int i = n - 1; i >= 0; i--) { for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; }

这段代码里有一处非常隐蔽的坑：当i和j相邻（即j = i + 1）且字符相等时，dp[i+1][j-1]变成dp[i+1][i]，这是一个左下角越界的非法区间。在 Java 里，dp[i+1][i]是合法下标，访问不会报错，值就是默认的0。0 + 2 = 2，恰好是正确答案（两个相同字符构成长度2的回文）。所以这段代码"侥幸"是对的。

但如果你用的是某些语言，或者你的初始化把dp[i+1][i]填成了别的东西，就会出错。更稳妥的写法是显式处理这个边界：

if (s.charAt(i) == s.charAt(j)) { dp[i][j] = (j - i == 1) ? 2 : dp[i + 1][j - 1] + 2; }

我倾向于写这个版本，因为它把"依赖非法区间"这件事显式化了，读代码的人不会困惑，换语言、换初始化方式也不会翻车。

3.2 最长回文子序列与最长公共子序列的等价关系

这道题还有一个非常巧妙的解法：把原串和它的反转串求最长公共子序列（LCS），结果就是最长回文子序列的长度。

为什么成立？直观理解是：回文子序列正着读和反着读是一样的，所以它既是原串的子序列，又是反转串的子序列；反过来，原串和反转串的任何一个公共子序列，如果长度取到最长，它一定对应一个回文结构。这个证明稍微有点绕，但作为解题工具非常好用，尤其是你已经写熟了 LCS 模板的时候。

public int longestPalindromeSubseq(String s) { String t = new StringBuilder(s).reverse().toString(); int n = s.length(); int[][] dp = new int[n + 1][n + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (s.charAt(i - 1) == t.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[n][n]; }

这个写法的好处是复用了 LCS 的正向遍历模板（i从小到大），脑子不用切换到区间DP模式；坏处是空间从 n² 变成 (n+1)²，常数略大。面试里我一般会先写区间DP版本，因为它是这道题的本意；如果面试官追问"还有别的思路吗"，再把 LCS 版本抛出来，效果往往不错。

3.3 一维滚动：pre变量的保存逻辑

516这道题空间压缩是值得做的，因为它依赖三个方向：dp[i+1][j-1]（左下）、dp[i+1][j]（下）、dp[i][j-1]（左）。压成一维之后，dp[j]在更新之前代表的是上一行（i+1）的值，更新之后代表当前行的值，所以dp[j-1]天然就是当前行已经算好的左邻居，而左下角那个值必须手动保存。

public int longestPalindromeSubseq(String s) { int n = s.length(); int[] dp = new int[n]; for (int i = n - 1; i >= 0; i--) { dp[i] = 1; int pre = 0; // 代表 dp[i+1][j-1] for (int j = i + 1; j < n; j++) { int tmp = dp[j]; // 先备份旧值，它就是 dp[i+1][j] if (s.charAt(i) == s.charAt(j)) { dp[j] = pre + 2; } else { dp[j] = Math.max(dp[j], dp[j - 1]); } pre = tmp; // 供下一轮 j 使用 } } return dp[n - 1]; }

pre这个变量的角色容易搞混，我在纸上推的时候是这么记的：当循环走到j的时候，pre里装的是"上一轮j-1时备份下来的旧dp[j-1]"，也就是dp[i+1][j-1]。这个对应关系一旦理顺，压缩版本跟二维版本就是完全等价的。

注意：dp[j] = Math.max(dp[j], dp[j-1])里的dp[j]是旧值（上一行），dp[j-1]是新值（当前行）。同一个数组里新旧混用，这是滚动数组最典型的陷阱，写的时候一定要在注释里写清楚哪个是哪个。

4. 动态规划收尾：把三十多道题压成五张状态设计图

训练营走到第56天，动态规划这一大块基本收官。回顾一下走过的路：从最基础的斐波那契、爬楼梯，到背包问题、打家劫舍、股票系列，再到子序列、编辑距离，最后落到回文系列。题目数量三十多道，但真正需要记住的状态设计模板其实只有五类。这个归纳不是为了偷懒，而是为了在新题面前能快速定位"它属于哪一类"。

这张表的价值在于：拿到一道新题，先对着表格找归属，找到归属之后，状态定义、遍历顺序、初始化方式基本都能照搬。这比背题解有用得多，因为题目会变，模式不会变。

4.1 五步法里真正决定成败的是第二步

大家都在说"动规五步法"：确定状态、确定递推、确定初始化、确定遍历顺序、举例推导。前两步人人都会背，但我观察下来，真正拉开差距的是第二步——递推式的推导，而不是状态定义。

原因在于：状态定义如果错了，做几个用例就能发现；但递推式写错，往往只在特定边界上出问题，非常难查。比如 516 里漏了j - i == 1的边界处理，在大多数用例上都能跑对，只有当你恰好碰到"两个相同字符相邻且是整个最长答案"的时候才炸。

我的做法是：写完递推式之后，立刻手动在纸上推一遍长度为1、2、3的所有区间，把二维表填出来，再对一遍代码逻辑。这个小习惯帮我挡掉了大量的边界错误，比事后 Debug 快十倍。

4.2 遍历顺序的判断依据，其实就一句话

"遍历顺序怎么定"是问得最多的问题，答案可以浓缩成一句：保证算当前状态时，它依赖的所有状态都已经算完。

这句话听起来像废话，但套到具体题目上非常管用：

• 01背包要倒序遍历容量，是因为dp[j]依赖dp[j-w]的旧值，正序会把同一件物品用两次；
• 完全背包要正序遍历容量，是因为它恰恰允许同一件物品用多次；
• 区间DP要从下往上、从左往右，因为依赖左下角；
• 双序列DP从小到大，因为依赖左上角。

四个场景，同一个判断标准。与其背"01背包倒序、完全背包正序"，不如把这句判断标准刻进脑子，遇到新题型也能自己推出来。

4.3 初始化不是填个0就完事

初始化被严重低估了。很多人在这一块吃亏，是因为把初始化当成了"填空默认值"，而实际上它是状态转移的边界条件，直接决定了递推链条的起点对不对。

举几个我在训练营里见过的典型翻车案例：

• 求"最小"的问题把dp初始化为 0，结果所有答案都是 0，因为min永远取到 0。正确做法是初始化为Integer.MAX_VALUE或者一个足够大的数。
• 求"方案数"的问题，dp[0]必须是 1 而不是 0，因为"凑出0元"有一种方案（什么都不选），这是乘法原理的起点。
• 背包问题里dp[0][0] = 0、其余dp[0][j] = -∞（求最大值且必须装满时），这个-∞的用意是"这个状态不可达"，不能省。

判断标准是：这个初始化值，在语义上代表什么？如果它代表"不可达"，那就要用极值；如果代表"空集的一种方案"，那就是1；如果代表"还没有任何贡献"，那才是0。

4.4 我自己踩过的几个典型坑，供你对照

第一个坑是把"子序列"和"子串"的转移方程搞混。这两个词在中文里只差一个字，但转移逻辑完全不同。子串类问题里s[i] != s[j]时直接判死，子序列类问题里还能取max抢救。我建议在纸上写题解的时候，把"连续"两个字用圈圈出来，强迫自己确认一遍。

第二个坑是二维数组的遍历顺序没有跟着依赖关系走。比如做双序列DP的时候习惯了i从1到n、j从1到m，某天遇到一道dp[i][j]依赖dp[i][j+1]的题就卡住了。这时候回到"依赖关系决定顺序"这句话，重新画图，问题就迎刃而解。

第三个坑是返回值取错位置。区间DP的答案通常是dp[0][n-1]，双序列DP是dp[n][m]，但有些变形题答案是整张表的最大值而不是角落那格。写完代码之后回头看一眼题目问的是什么，能避免大量无谓的调试。

第四个坑，也是最容易忽略的：字符串下标和DP下标错位。双序列DP里dp数组开的是n+1大小，dp[i][j]对应的是s的前i个字符，所以取字符的时候要写s.charAt(i - 1)。这个-1忘了写，在某些用例上依然能过，但答案是错的。

4.5 从这五类模板往外延伸的路线

动态规划学到这个阶段，基础题型基本已经覆盖完了，剩下的扩展方向大致有三个。

一是状态压缩，也就是把二维压成一维，再往上就是状压DP（用二进制整数表示集合状态），典型题目是"旅行商问题"和"集合覆盖"类。这一块的门槛不在思路，而在于对位运算的熟练度。

二是树形DP，状态定义在树的节点上，转移靠后序遍历，典型题目是"打家劫舍III"和"二叉树的最大路径和"。树形DP的关键是搞清楚"这个节点的状态，需要从子节点汇总什么信息"。

三是数位DP和概率DP，这两类在实际面试里出现频率不高，但在竞赛里很常见。数位DP的核心是把"统计某个范围内满足条件的数的个数"拆成"从高位到低位逐位确定"。

不过说实话，我不建议在这个阶段急着往外扩。把线性、背包、双序列、区间、状态机这五类的每一道题都手写一遍，比刷十道新题型有用得多。我自己复盘的时候发现，那些真正在面试里卡住我的题，往往不是没见过的类型，而是见过的类型里我没吃透的边界。

5. 回看这两道回文题，它们教会我的事

把647和516放在一起看，最能说明动态规划里一个朴素但深刻的道理：题目描述上的一点微小差异，会沿着状态定义一路放大，最终变成完全不同的代码结构。

647里s[i] != s[j]是死刑，516里是转机。这个差异源于"连续"这个约束——连续意味着你不能跳着选，所以两端对不上就彻底没戏；不连续意味着你有取舍的自由，所以可以退而求其次。约束越强，转移越简单；约束越松，转移的分支越多，这个规律在背包问题里也成立（01背包比完全背包约束强，但转移反而更简单）。

还有一个体会是关于"表的方向感"。做了这么多区间DP之后，我现在拿到一道新题，第一反应不是想递推式，而是先在纸上画一张表，标出每个格子依赖哪几个邻居。这个动作看起来笨，但它把"遍历顺序"这个最容易出错的部分变成了一个纯几何问题——只要所有箭头都从"已算"指向"未算"，顺序就对了。

最后分享一个小技巧，是我自己做区间DP时的固定动作：在写代码之前，先手填一张 4×4 的小表。比如对"abba"手动算出dp[0][3]，把中间每一步的值都写下来，然后再写代码，最后用打印语句对一遍。这四分钟的手工推演，能挡掉九成的边界错误，比事后加一堆if判断要划算得多。字符串长度小的时候手工推演成本极低，而错误暴露得极早，这个投入产出比在所有调试手段里是最高的。

动态规划这一模块到这里告一段落，回文这两个题算是收官之作，也是区间DP最好的入门材料。往后不管是做切分回文、构造回文、还是回文相关的计数问题，这套"区间 + 端点 + 剥洋葱"的思路都能直接套用。