企业官网建设流程全解析

1. 先搞清楚题目到底在问什么，别急着写代码

做动态规划专题做到第四十五天，最大的感受是：题目难度不一定和数据规模成正比，真正让人卡住的往往是“题目本身要求什么”这件事没想明白。647和516这两道题，名字长得像，解法也都在同一个dp框架里，但一个是判断存在性，一个是计算最优长度，思维路径完全不同。

1.1 回文子串：统计的是连续片段的数量

647题输入一个字符串s，输出回文子串的个数。注意这里的“子串”必须是连续的。比如s="abc"，那么子串只有"a"、"b"、"c"、"ab"、"bc"、"abc"这六种，其中回文的是三个单字符，答案就是3。

这个“连续”是理解整道题的关键。因为要求连续，你才能用一个区间[i, j]去表示一个子串，也才能用“掐头去尾”的方式来递推判断回文。如果换成了子序列，连续这个约束没了，整个状态定义都得换，那就是516题的事了。

我还记得第一次做这题时，想着能不能用前缀hash加二分去统计，后来发现虽然能过，但思路很绕，而且边界条件一大堆。刷算法营到这个阶段，其实最该练的是“看到题目的特征，能快速映射到对应的算法套路”。回文子串的连续区间特征，天然对应二维区间DP或者中心扩展，这才是第一反应应该有的东西。

1.2 最长回文子序列：允许跳着选字符，只求最大长度

516题要求从字符串s中选出一个子序列，使它是回文的，并且长度最长。子序列不要求连续，只要相对顺序不变就行。比如s="bbbab"，答案不是"bbb"这种连续片段，而是"bbbb"，因为你可以跳着取下标0、1、3、4，拼成四个b。

这里一定要扭转之前做“子串”题目留下的惯性：没必要要求你选中的字符在原字符串里挨在一起。这也意味着，判断区间[i, j]内的最优回文子序列时，即使s[i]和s[j]不相等，你仍然有机会通过丢弃其中某一个字符来保留更优解。这种“丢弃一端继续找”的思路，是516题和647题最本质的差异。

所以先花五分钟在草稿纸上把这两个公式写出来：

• 647：在判断“以i开头j结尾的这段连续字符是不是回文”，答案是布尔值。
• 516：在求解“从i到j这段范围内最多能挑出多长的回文子序列”，答案是长度。

定了这个基调，后面所有dp数组、转移方程、初始化的设计都会顺很多。

2. 暴力枚举的成本到底有多高，为什么必须动态规划

每次写动态规划题，我都会先估算一下暴力解法的时间复杂度，不是为了证明暴力不可用，而是为了让自己理解dp究竟优化掉了什么。这两道题放在一起看特别合适，因为它们暴力解法的瓶颈各不相同。

2.1 统计回文子串：枚举区间加逐位校验

最直观的暴力做法是：双重循环枚举所有子串的起点i和终点j，然后写一个函数判断s[i..j]是否回文。枚举区间是O(n^2)，判断回文最坏是O(n)，所以总复杂度是O(n^3)。当字符串长度到1000左右时，这个复杂度在一秒量级下基本跑不完。

看到O(n^3)的时候，常规的优化思路会是：能不能把判断回文的O(n)省掉？于是你自然想到，可以先判断短的区间，然后把结果存下来，等判断长区间时直接用。这其实就是动态规划的雏形——保存小区间的回文状态，避免重复扫描。

我用一个例子说明这种重复计算：s="abcba"，判断整个字符串是否回文，最内层要比较a和a、b和b、c和c。而判断"bcb"的时候，又比较了b和b、c和c。同一个c被反复比较了三次。一旦把“bcb是回文”这个结果缓存下来，外层判断"abcba"时只查一次表就够了。

2.2 找最长回文子序列：枚举子集是指数爆炸

子序列就不一样了。一个长度为n的字符串，子序列总数是2^n个，因为每个字符都有选或不选两种可能。n=20就已经有上百万个组合，n=30更是超过十亿。这完全没法直接枚举。

就算你用回溯加剪枝，也逃不过指数级别的搜索空间。这时候动态规划的优势就极其明显：它把指数问题通过重叠子结构压缩成了O(n^2)的区间递推。本质上是把“选了哪些字符”这个巨大的状态空间，压缩成“区间左端点和右端点”两个维度。

所以以后看到回文相关题目，如果题目给出的是10^3甚至10^4级别的字符串长度，基本可以直接锁定动态规划、中心扩展这类O(n^2)解法。指数级的搜索连边都摸不到。

3. 647 回文子串：布尔dp的细节都在遍历顺序里

647题的dp设计非常经典，几乎所有讲解回文区间的文章都会拿它当入门题。但我在刷题营里发现，真正让很多人卡住的不是状态定义，而是两层循环的遍历顺序。这题我前后写错过两次，必须单独拉出来说说。

3.1 dp[i][j]的含义与转移逻辑

定义dp[i][j]为布尔值，表示字符串s从下标i到下标j这段连续子串是否为回文。初始时所有dp[i][j]都是false，只有满足条件才置为true。

转移时分三种情况讨论：

1. i == j，即单个字符，一定是回文，dp[i][j] = true。
2. j == i + 1，即两个字符相邻，只要s[i] == s[j]，那么这两个字符组成的子串就是回文。
3. j > i + 1，此时整个子串是否回文，取决于两端字符是否相等，以及中间部分s[i+1..j-1]是否回文，即dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]。

在写代码时可以把前两种情况合并：如果s[i] == s[j]并且j - i <= 1，直接置true；如果j - i > 1，就查dp[i+1][j-1]。

统计答案很简单，每次dp[i][j]为true，计数器加1即可。最终return计数。

下面给一个Python核心代码段，方便对照：

def countSubstrings(s: str) -> int: n = len(s) if n == 0: return 0 dp = [[False] * n for _ in range(n)] ans = 0 for i in range(n - 1, -1, -1): for j in range(i, n): if s[i] == s[j]: if j - i <= 1: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] if dp[i][j]: ans += 1 return ans

这段代码的循环写法不是随手写的，遍历顺序是这题的重中之重，下面详细解释。

3.2 为什么i必须从大到小，j从小到大

看转移方程，dp[i][j]依赖的是dp[i+1][j-1]，也就是说，要计算某个位置的答案，必须保证它的“左下角”已经被计算过。如果把i从0往n-1遍历，j从i往n-1遍历，会发生什么？以i=0为例，计算dp[0][2]时需要dp[1][1]，但此时i=1那一行还没开始遍历，dp[1][1]是初始值false，结果就会错判。

反过来，让i从n-1往0遍历，也就是从下往上计算每一行，同时j从i往n-1遍历，从左往右填充当前行，就能保证用到dp[i+1][j-1]时它已经算好了。因为左下角所在的i+1行在下一行，已经被外层循环先跑过。

我经常用这个类比帮助记忆：dp计算顺序要像填表格时“从下往上，从左往右”地扫，而不是按阅读习惯从上往下。很多人写错的根源就是把“阅读顺序”带到了“计算顺序”里。

3.3 单独说说中心扩展法，作为对照更理解dp

647题其实还有一个不需要二维数组的解法：中心扩展。枚举每个回文中心，然后向两边扩展，统计能扩出多少个回文子串。中心有两种：一个字符（奇数长度回文）和两个字符（偶数长度回文），所以中心总数是2n-1个。

中心扩展的时间复杂度同样是O(n^2)，但空间是O(1)。我做过性能对比，在n=1000时二者差距不大，n=5000时中心扩展明显更快，因为数组访问次数更少。那dp还有存在意义吗？当然有。dp的思维方式更通用，一旦题目变成“不仅要个数，还要构造结果”或者“给出多个查询”，dp的预处理优势就会体现出来。

学习时不要只背一种解法，两题放在一起时我建议先写dp，再把中心扩展当优化技巧掌握。这样既理解本质，又知道怎么应急。

4. 516 最长回文子序列：把转移方程一步步推到你自己都信

516题的状态定义和647很像，一开始很容易照搬过来，设dp[i][j]为“从i到j这段子串的最长回文子序列长度”。这个方向是对的，但转移方程推起来要更绕一点，我甚至觉得这题的核心难点已经从“写代码”转移到了“说服自己为什么这个转移一定正确”。

4.1 状态定义与相等情况

dp[i][j]表示s[i]到s[j]这段区间内，能挑出的最长回文子序列长度。初始化时，dp[i][i] = 1，因为单个字符本身就是长度为1的回文子序列。

当s[i] == s[j]时，这两个字符可以同时被纳入回文子序列的两端，那么dp[i][j] = dp[i+1][j-1] + 2。这个逻辑要仔细想想：既然两端字符相同，把它们同时选上一定不会亏，因为中间部分s[i+1..j-1]的最优回文子序列长度就是dp[i+1][j-1]，再加上这两个相同的字符，长度必然最长。

这里有个反直觉的细节：即使dp[i+1][j-1]是0，加上2之后也可能比单纯只取一端更大。比如s="aa"，i=0, j=1，dp[1][0]不存在但可以视为0，结果dp[0][1] = 2，完全正确。

4.2 不相等情况：只能二选一

当s[i] != s[j]时，情况就复杂了。此时i和j不可能同时作为最长回文子序列的两端，因为两端字符不同，把它俩都选进去必然无法构成回文。所以最优解要么出现在丢掉s[i]后的区间[i+1..j]里，要么出现在丢掉s[j]后的区间[i..j-1]里。

转移方程写作：dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

理解这个方程的关键在于：你要处理的不是一个必须使用所有字符的约束问题，而是一个“可选可不选”的子序列问题。丢掉一端不会影响内部子序列的完整性，只是让可选范围缩小了。所以取两个子问题的较大值，就是当前区间的最优值。

以s="cbbd"为例，期望输出是2（"bb"）。手动推一下：

• dp[0][0] = 1, dp[1][1] = 1, dp[2][2] = 1, dp[3][3] = 1
• dp[1][2]中s[1]='b', s[2]='b'相等，所以dp[1][2] = dp[2][1] + 2 = 2
• dp[0][3]中s[0]='c', s[3]='d'不等，所以dp[0][3] = max(dp[1][3], dp[0][2])。
• dp[1][3]中s[1]='b', s[3]='d'不等，继续取max；dp[0][2]中s[0]='c', s[2]='b'不等，继续取max。
• 最终会推回dp[1][2]=2，得出答案2。

整个递推过程就体现了区间DP的特点：大区间的答案完全由更小区间的答案组合出来，只不过这种组合不一定像回文子串那样只依赖一个方向。

4.3 初始化和遍历方向的完整代码说明

516的初始化除了dp[i][i]=1之外，还要注意dp[i][j]在j < i时无意义。实现时可以让j从i+1开始遍历，避免覆盖初始化值，同时也不会访问到无效状态。

遍历顺序依然是从下往上、从左往右。因为dp[i][j]依赖dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]，这三个位置分别在当前格的左下、正下、左方。只有让i从大到小、j从小到大，才能保证这三个角度的值都已被计算。

Python代码如下：

def longestPalindromeSubseq(s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)] for i in range(n - 1, -1, -1): 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]

这里dp[i+1][j-1]在j == i+1时访问的是dp[i+1][i]，也就是j<i的无效位置，但此时由于s[i]==s[j]，而且它们是相邻字符，直接计算得到2。在Python中dp[i+1][i]虽然存在但值为0，所以结果是2，刚好正确。不过依赖这个默认值总归有点隐晦，我在代码里显式判断一下更稳妥：

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

这个边界看起来很没存在感，但第一次写的时候我就是因为没处理它，在字符串长度为2且字符相同时得到1，差点以为整个方程错了。排查了很久才发现是边界行为，特此提醒。

5. 两题放在一起对照，才真正理解子串和子序列的思维差异

刷题最忌“今天做647，明天做516，然后分别记住两种模板”。这两道题放在同一天，本身就是希望你能在对比中提炼出更通用的方法论。我在复盘时做了一张对照表，每次做相关题目前都会看一眼。

这张表里有几个值得细看的地方：

第一，647中的“中间必须是回文”是硬约束，因为子串本身连续，只要里面有一段不是回文，整体就不可能回文。但516不需要检查中间，因为子序列可以跳过中间的字符，只要两端相等，内部怎么乱都能通过跳选来凑出回文。这就是为什么同样s[i]==s[j]，一个要看dp[i+1][j-1]是否为true，另一个可以直接+2。

第二，647的答案不是dp[0][n-1]，而是所有区间中true的数量之和。因为要求的是个数，不是最长长度。不少初学者上手写完之后直接return dp[0][n-1]，结果和答案差一大截，原因就是没分清“存在性”和“最优值”。516则天然是“最优值”问题，答案自然落在最后一个格子上。

第三，647的dp数组可以理解为一张“回文关系图”，每个true单元都是一个合法回文子串；516的dp数组则是“长度累积表”，每个格子保存的是该区间内的最优解。前者重判断，后者重计算。

从这两题还能延伸出一个通用结论：连续子串类的回文DP，几乎都是“判断型布尔DP”，而子序列类的回文DP，几乎都是“区间最优值DP”。以后遇到类似“多少个回文子串”的问题，先想布尔dp；遇到“最长回文子序列”或“最长回文字符串长度”的问题，再考虑数值dp。

5.1 空间优化的进阶思路

两题都用二维数组，空间都是O(n^2)。在实际面试中，如果面试官追问空间优化，可以从这里入手。

647的转移只依赖dp[i+1][j-1]，也就是下一行的左一列。如果按i倒序遍历，其实可以只保留一行，但仍然要处理j-1方向，因为dp[i][j]还包含对dp[i][j-1]的依赖吗？并不依赖，它只依赖dp[i+1][j-1]。所以理论上可以用一维数组，但问题在于：当前行的j从左向右遍历时，dp[j-1]存的是当前行的值还是下一行的值？如果内层j从小到大，dp[j-1]在这一轮已经被更新成当前行，而dp[i+1][j-1]需要的是下一行的旧值，这就冲突了。所以647的空间压缩不太直接，需要引入额外变量或改变内层方向。我的建议是二维先行，空间优化放到理解透彻后再考虑。

516则不同，它同时依赖三个方向，滚动数组会更容易处理。可以用两个一维数组分别保存当前行和下一行，每次更新前把下一行复制过来。这样空间降到O(n)，代码量增加不多。实际做下来，对于n=1000的数据，二维数组和滚动数组时间差异很小，所以优化的核心价值在于内存而不是速度。

6. 刷题营第四十五天的踩坑记录，希望能帮你少走弯路

最后分享几个我实际做这两道题时踩过的坑。这些问题不是知识点本身，但恰恰是它们决定了你能否在限定时间内AC。

6.1 遍历顺序写反，运行结果玄学出错

我第一次做647时，顺手写成了i从0到n-1，j从i到n-1，结果在小样例上居然偶尔正确，到了长一点字符串就开始漏数。原因是短字符串里很多区间在遇到s[i]==s[j]且j-i>1时，中间区间不一定被提前算到，就会漏判。

这种“部分样例能过、长样例就挂”的体验非常折磨人。当时我把所有字符逐个打印观察，才发现是计算顺序问题。从那以后，凡是写区间dp，我会先问自己一个问题：dp[i][j]依赖哪些位置？这些位置在我的循环顺序里是否已经计算完成？把这个问题在注释里写出来，基本就不会再错。

6.2 j的范围从i开始还是i+1开始，跟初始化有关

很多人做647时j从i开始，因为单个字符也要计数；做516时反而写j从i开始，把dp[i][i]=1的初始化覆盖掉，然后结果double count。我的建议是647里j从i开始没问题，因为每个单字符都是答案的一部分；516里j从i+1开始，因为dp[i][i]=1要在初始化阶段统一设置，不要在循环里重复处理。两种写法都能过，但务必保持一致，别混着用。

6.3 用打印dp表的方式验证推理过程

如果你发现自己推的转移方程在小样例上不对，最快的排查方式不是空想，而是把dp表打印出来手动走一遍。比如拿s="aba"跑647，期望输出3，分别对应三个起始位置不同的单字符和"aba"。我打印dp表后能看到dp[0][2]为true，而这个true正是建立在dp[1][1]为true的基础上。一旦循环顺序写错，dp[1][1]是false，dp[0][2]也会变成false，肉眼一眼就能发现。

516也一样，打印dp表后能直观看到长度如何从对角线上的1，一层层扩散到右上角。这种可视化对理解区间DP帮助极大，胜过看十遍理论讲解。

刷到第四十五天，动态规划已经不再是单纯套模板的阶段了。回文类问题的价值不在于题目本身，而在于它强迫你去区分“状态含义”和“依赖关系”这两个最容易混淆的东西。647和516一天做完，我最大的体会是：dp[i][j]到底存什么、依赖什么、怎么遍历，这三个问题想透了，代码基本就是翻译一遍而已。希望这篇记录也能让你少花一点在调试循环顺序上的时间。