企业官网建设流程全解析

刷题进度走到第四十八天，动态规划这部分已经进入“子序列”专题。今天这三道题放在一起非常有意思：最长递增子序列、最长连续递增序列、最长重复子数组，表面看都是求“最长”，但一个不连续、一个连续、一个跨两个数组连续。很多人在这个阶段开始迷糊，不是因为题目本身多难，而是状态定义稍微差一点，代码就完全对不上。我自己当初刷的时候，最长递增子序列反复改了三遍才想明白“为什么dp[i]一定要表示以nums[i]结尾”，最长连续递增序列又差点用双重循环把简单问题复杂化，到了最长重复子数组更是踩中了滚动数组覆盖顺序的坑。这篇文章就把这三道题当一个整体来拆，讲清楚每道题的DP设计逻辑、代码怎么落地，以及对比起来最值得记住的共性与差异。适合正在上算法训练营、或者准备面试手撕动态规划的同学读。

1. 先看清题目差异：同一个“最长”，三种不同的约束

1.1 子序列和子数组，第一件事先分清概念

最长递增子序列里的“子序列”意味着可以选择原数组中任意位置的元素，只要保持相对顺序，中间跳掉几个元素完全没问题。比如数组 [10, 9, 2, 5, 3, 7, 101, 18]，最长递增子序列是 [2, 3, 7, 101]，长度为4，但它并不是原数组里紧挨着的一段，中间的数字被跳过了。

最长连续递增序列则完全不同，“连续”二字直接限定死了：子序列必须是原数组里连续的一段。比如 [1, 3, 5, 4, 7] 中，[1, 3, 5] 是连续递增的，长度为3，而 [1, 3, 5, 7] 虽然递增，但因为中间隔着4，不能算连续递增序列。

最长重复子数组的“子数组”同样是连续的概念，只不过现在是两个数组之间找公共部分。比如 [1, 2, 3, 2, 1] 和 [3, 2, 1, 4, 7]，最长公共连续片段是 [3, 2, 1]，长度为3。这里“公共”加“连续”两个约束叠加，状态设计就比单数组复杂不少。

1.2 为什么训练营要把这三题放在同一天

这三题恰好覆盖了子序列/子数组DP最常见三种形态：单数组不连续、单数组连续、双数组连续。如果只做一道题，你可能会背下那一道的转移方程，但只有放在一起对比，才能真正理解状态定义里的“锚点”有多重要。三道题的核心套路都是“以某个位置结尾”来定义dp状态，但因为连续性和数组数量的不同，转移范围、状态维度、代码细节全都不一样。

我个人的体会是，第四十八天真正要练的不是“会做三道题”，而是建立一种条件反射：拿到一个子序列/子数组题，先问自己“连续吗”“几个数组”，再决定状态维度和转移方向。这一步想清楚，代码往往就是模板套用。

2. 300.最长递增子序列：从“不连续”理解为什么要定义成以i结尾

2.1 思路推导：递增子序列的“接力棒”

最长递增子序列的经典定义是：dp[i] 表示以 nums[i] 这个元素结尾的最长递增子序列长度。

为什么非要“以 nums[i] 结尾”，而不是“前 i 个元素中能形成的最长递增子序列长度”？这是这道题最值得琢磨的点。因为子序列允许跳着选，如果我们只知道前 i 个元素中的最长长度，却不知道这个“最长序列”最后选的元素是谁，就没办法判断当前这个 nums[i] 能不能安全地接在后面。递推需要的是“能接上的信息”，也就是上一个序列的最后一个元素。

反过来，定义成“以 nums[i] 结尾”之后，想扩展一个递增子序列就很简单：我只需要在 i 前面找一个下标 j，满足 nums[j] < nums[i]，然后把 nums[i] 接到以 nums[j] 结尾的序列后面。以 nums[i] 结尾的长度，就是从所有这样的候选 j 中取最大值再加1。

初始状态下，每个元素自己单独就能构成一个长度为1的递增子序列，所以 dp 数组全部初始化为1。

2.2 状态转移方程与一个完整的手算过程

转移方程可以写成：

dp[i] = max(dp[i], dp[j] + 1) 其中 0 <= j < i 且 nums[j] < nums[i]

这里 j 的取值范围是 i 之前的所有位置，因为不连续，任何前面的元素都有可能是上一段序列的结尾。

拿一个简单例子手算一遍，nums = [1, 3, 2, 4]：

• 初始化 dp = [1, 1, 1, 1]
• i = 1，nums[1] = 3，j 只能取0，nums[0] = 1 < 3，dp[1] = dp[0] + 1 = 2
• i = 2，nums[2] = 2，j = 0 时 1 < 2，dp[2] = dp[0] + 1 = 2；j = 1 时 nums[1] = 3 >= 2，不能用。dp[2] = 2
• i = 3，nums[3] = 4，j = 0 给 dp[0]+1 = 2，j = 1 给 dp[1]+1 = 3，j = 2 给 dp[2]+1 = 3，取最大 dp[3] = 3

最终 dp = [1, 2, 2, 3]，答案取最大值3。最长递增子序列可以是 [1, 2, 4] 或 [1, 3, 4]，都满足。

2.3 代码实现

def length_of_lis(nums): if not nums: return 0 dp = [1] * len(nums) ans = 1 for i in range(1, len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) ans = max(ans, dp[i]) return ans

时间复杂度 O(n^2)，空间复杂度 O(n)。如果 nums 为空数组，直接返回0，这个边界条件虽然简单但很容易漏。

2.4 两个容易踩的细节

第一个细节：最终答案是 dp 数组里的最大值，不是 dp[-1]。很多人习惯性返回最后一个状态，但最长递增子序列完全可能以数组中间的某个元素结尾。比如 nums = [1, 2, 3, 0, 1]，dp[-1] 对应的序列 [0, 1] 长度只有2，而正确结果是3。所以我会在每次更新 dp[i] 之后同步维护 ans，而不是最后再去 max。

第二个细节：如果题目改成非严格递增，也就是允许相等元素连续，那么判断条件要从 nums[j] < nums[i] 改成 nums[j] <= nums[i]。这个变化会导致整个转移行为完全不同，写代码前一定要和面试官确认题意。

3. 674.最长连续递增序列：连续让问题突然变得很“短”

3.1 和300题的核心区别：转移范围收窄了

最长连续递增序列的定义和300题很像，但多了“连续”二字。正因为必须连续，当前元素 nums[i] 能否扩展出一个更长的序列，只取决于它和前一个元素 nums[i-1] 的大小关系，不需要再回头枚举 i 之前的所有位置。

如果 nums[i] > nums[i-1]，那么以 nums[i] 结尾的连续递增序列长度，可以直接在以 nums[i-1] 结尾的连续递增序列长度基础上加1。因为连续递增序列里 nums[i-1] 必须紧跟在 nums[i] 前面，它是唯一的候选前驱。反过来，如果 nums[i] <= nums[i-1]，连续递增就断了，以 nums[i] 结尾的序列只能从当前位置重新开始，长度为1。

这个差异带来的收益很明显：300题是双重循环，674题只需要单次遍历，时间复杂度直接从 O(n^2) 降到 O(n)。

3.2 一维DP写法，以及更省空间的滚动写法

用 dp[i] 表示以 nums[i] 结尾的最长连续递增序列长度，转移是典型的分支结构：

def find_length_of_lcis(nums): if not nums: return 0 dp = [1] * len(nums) ans = 1 for i in range(1, len(nums)): if nums[i] > nums[i - 1]: dp[i] = dp[i - 1] + 1 ans = max(ans, dp[i]) return ans

由于 dp[i] 只依赖 dp[i-1]，连 dp 数组都可以省掉，只用一个变量记录“当前连续递增长度”，碰到递减或相等就重置为1。这种空间优化在面试现场非常好用，写出来也更干净：

def find_length_of_lcis(nums): if not nums: return 0 cur = 1 ans = 1 for i in range(1, len(nums)): if nums[i] > nums[i - 1]: cur += 1 else: cur = 1 ans = max(ans, cur) return ans

手动模拟 [1, 3, 2, 4]：cur 依次为1、2（1<3）、1（3>2不成立重置）、2（2<4），最终 ans=2。注意这里最长连续递增序列是 [1,3] 或 [2,4]，长度都是2。

3.3 为什么不要套用300题的双重循环

我在评论区看到过有人把674题写成300题的解法，也过了。逻辑上并不是完全错，但属于“杀鸡用牛刀”。双重循环能处理不连续的情况，自然也能处理连续的情况，因为它是在更宽松的约束下做枚举。但这样做有两个问题：一是时间复杂度多了一个 n，数据规模一大就会超时；二是丢失了“连续”这个条件本身带给我们的优化线索。算法题最值钱的就是发现约束带来的结构，674题的结构就是相邻比较，抓住这一点，代码量和维护成本都会小很多。

一个更隐蔽的易错点：有人会把 dp[i] 理解成“前 i 个元素中能形成的最长连续递增序列长度”，然后觉得转移应该写成 dp[i] = max(dp[i-1], 延续长度)。这种定义不是不行，但会引入额外变量去记录当前连续段的长度，代码反而绕了。还是坚持“以 i 结尾”的锚点最顺手。

4. 718.最长重复子数组：二维DP与滚动数组的翻车现场

4.1 双数组连续问题，状态要定义成“公共后缀”

最长重复子数组要在两个数组之间找一个最长的公共连续片段。这类双数组问题的通用状态设计是二维DP：dp[i][j] 表示以 nums1 的第 i-1 个元素结尾、以 nums2 的第 j-1 个元素结尾的最长公共子数组长度。

为什么又是“以...结尾”？因为连续片段要拼接，必须保证最后两个元素相等，才能把前面的公共部分延续过来。如果最后两个元素不相等，那么以这两个位置结尾的公共子数组长度就是0，不管前面有多少匹配都没用，因为“连续”断掉了。

这里还要注意一个细节：dp数组我一般会开成 (n+1) x (m+1)，多出一行一列作为哨兵，dp[0][...] 和 dp[...][0] 全是0。这样当 i=1 或 j=1 时，dp[i-1][j-1] 就是 dp[0][0] 或 dp[0][j]，能统一处理边界，不用写一堆判断。

4.2 二维DP的转移逻辑与代码

转移方程非常简单：

if nums1[i-1] == nums2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = 0

注意两个数组下标都减1，是因为多开了一行一列。

def find_length(nums1, nums2): n, m = len(nums1), len(nums2) dp = [[0] * (m + 1) for _ in range(n + 1)] ans = 0 for i in range(1, n + 1): for j in range(1, m + 1): if nums1[i - 1] == nums2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 ans = max(ans, dp[i][j]) # else 保持 0 return ans

比如 nums1 = [1, 2, 3, 2, 1]，nums2 = [3, 2, 1, 4, 7]。当 i=3、j=1 时 nums1[2]=3，nums2[0]=3，相等，dp[3][1] = dp[2][0] + 1 = 1；接着 i=4、j=2 时 nums1[3]=2，nums2[1]=2，dp[4][2] = dp[3][1] + 1 = 2；再下一组 i=5、j=3 时 nums1[4]=1，nums2[2]=1，dp[5][3] = dp[4][2] + 1 = 3。最终答案就是这个3。

复杂度是 O(n * m)，空间也是 O(n * m)。

4.3 滚动数组优化：倒序遍历是不够的，记得清零

二维DP可以压缩成一维。因为 dp[i][j] 只依赖左上方的旧值 dp[i-1][j-1]，我只需要在遍历一维数组时保留“上一行”的结果。但如果内层 j 正序遍历，dp[j-1] 可能已经被当前行覆盖掉，再到 dp[j] 时用的就不是上一行的 dp[j-1] 了。所以内层 j 必须从后往前遍历。

def find_length_optimized(nums1, nums2): m = len(nums2) dp = [0] * (m + 1) ans = 0 for i in range(1, len(nums1) + 1): for j in range(m, 0, -1): if nums1[i - 1] == nums2[j - 1]: dp[j] = dp[j - 1] + 1 ans = max(ans, dp[j]) else: dp[j] = 0 return ans

这里最容易被忽略的是 else 分支的 dp[j] = 0。如果不显式清零，dp[j] 会保留上一行留下的旧值。一旦某个位置不相等，按理说以这两个位置结尾的公共子数组长度应该断开为0，但旧值还在，后续匹配就会把这个错误长度继续传递下去。我第一次写滚动数组时就漏了这行，结果样例能过，大数组全错。

顺带一提，718题和经典的最长公共子序列问题不是一回事。最长公共子序列不要求连续，转移时要考虑“不选某个位置”的情况，也就是 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。而最长重复子数组要求连续，所以不相等时直接归零，这两种转移差异要区分开，面试时经常被拿来连环追问。

5. 三题横向对比：动态规划子序列题的答题套路

5.1 状态定义的高度统一：都锚定“以某个位置结尾”

把三道题的状态定义放在一起看：

共同点非常明显：全都锚定在“结尾”。这不是巧合，而是所有子序列/子数组DP的基本功。只要状态描述了结尾元素，递推时就能明确判断“当前元素能不能接到前面的序列上”。

5.2 连续与不连续，直接决定转移范围

这个规律非常实用：连续性越强，转移范围越小。遇到不连续题目，第一反应是枚举前面所有可能的状态；遇到连续题目，第一反应是看相邻位置或者上一行同一对角线的状态。

5.3 初始化与最终答案的对比

三道题的初始化也遵循同样的套路：

• 单数组子序列：每个元素单独成序列，所以 dp[i] = 1。
• 双数组子数组：空数组之间没有公共部分，所以哨兵行和哨兵列全部为0。
• 最终答案统一是 dp 数组里的最大值，而不是最后一个状态。

这个“答案要取max”的坑真的太常见了。因为最长序列不一定停在原数组末尾，这在300题和674题里都一样，718题也不能只看 dp[-1][-1]。

5.4 一个可以直接套用的手写框架

如果面试碰到类似题目，我会在脑子里快速过这个框架：

1. 判断连续或不连续 -> 决定转移时需要枚举还是只看相邻 2. 判断是单数组还是双数组 -> 决定状态是一维还是二维 3. 定义 dp，锚定“以某个位置结尾” 4. 初始化：单数组填1，双数组填0（多开哨兵行列） 5. 转移：能接上就 +1，接不上就重置为 1 或 0 6. 答案：全程维护 max，而不是最后取 dp[-1]

这个框架不保证能解所有DP题，但在“子序列/子数组”这个分类里非常能打。

6. 实战中容易翻车的细节与排查思路

6.1 返回值问题：到底返回 dp[-1] 还是 max(dp)

先说结论：这三道题都要返回 max(dp)。为什么有人会返回 dp[-1]？因为做路径类DP做习惯了，总觉得最后一个状态包含全局最优。但子序列问题里，最优解可能结束在任何一个位置。比如 nums = [2, 3, 1]，最长递增子序列是 [2, 3]，以第2个元素结尾，dp[-1] 对应的是以1结尾的序列，长度只有1。

排查方式很简单：先在纸上跑一个小样例，确认最优序列的结尾位置，再去代码里看答案取的是不是覆盖到那个位置。

6.2 滚动数组覆盖顺序：为什么718一定要倒序

一维滚动数组本质上是把二维表格压缩成一行，但每次更新 dp[j] 时，它右边的状态（j+1、j+2...）还需要用上一行的旧值。正序遍历会把 dp[j-1] 提前更新成当前行的值，后面的 dp[j] 再用时，就混入了当前行信息。

我可以给你一个更直接的排查思路：出现“重叠累加”现象时，比如某个公共片段的长度被加了两次，第一个怀疑对象就是滚动数组的遍历方向。

同时再次强调：else 分支清零不能漏。很多滚动数组写错，不是方向问题，而是“断开后应该归零却没有归零”。

6.3 严格递增和非严格递增的歧义

300题和674题都说“递增”，默认含义是严格递增，也就是 nums[j] < nums[i] 或 nums[i] > nums[i-1]。如果改成允许相等，判断条件就要变成 <= 或 >=。这类题在面试里经常被作为一个追问点，别默认，先问清楚最好。

6.4 常见问题速查表

7. 第四十八天刷完，我最想提醒你的一件事

三题放到一起刷完，我最大的感受是：动态规划题最怕的不是递推公式难想，而是状态定义草率。300题如果把状态定义成“前i个元素里的最长递增子序列长度”，每一步都会卡在“当前元素到底能不能接上”这个问题上。想通了“以谁结尾”之后，674题和718题基本就是同一套思维的不同变体，难度瞬间降下来。

建议你在刷完这三题之后，自己在纸上画一遍 dp 表格，不要只盯着代码。30分钟的花费，能把“为什么连续和不连续转移不一样”“为什么二维DP要取左上角”“为什么滚动数组要倒序”这几个问题一次性想透。这个思维习惯，对你后面做编辑距离、回文子串、戳气球这类复杂DP题都会有很直接的帮助。我自己在第四十八天这个节点上，最大的收获不是记住了三道题，而是终于建立了“先定锚点再写转移”的习惯。哪怕题目换了一百遍，只要这个习惯在，手撕DP就不慌。