最近刷到每日一题里的“三段式数组 II”，标题后面括号里写着“解法二：DP”。第一眼看到还挺感兴趣，因为我印象中第一版解法用两个分割点暴力枚举，逻辑不难但复杂度太难看。这个第二版解法换成动态规划的思路以后，代码量反而少了一截，跑起来也从“勉强能过”变成“轻松跑满”。这篇就把我对这个 DP 解法的完整拆解、推导过程和踩坑记录写出来，给同样在啃这道题的同学一个参考。
先把题目通俗地翻译一下：给定一个数组，让我们用两个分割点把它切成三段连续的非空子数组，切完之后每一段都要满足某个“合格条件”。在这道题里，我按最常见的约束来演示，也就是每一段元素之和都不能超过给定的上限 K。题目最终要的是满足条件的切法总数。暴力做法很简单：第一层的 i 表示第一段结束位置，第二层的 j 表示第二段结束位置，然后分别检查三段是否满足条件。这个 O(n²) 的做法数组规模小的时候没问题，一旦 n 上万就明显扛不住。解法二用 DP 加滑动窗口，把复杂度压到 O(n)，这也是为什么我推荐优先理解解法二的原因。
1. 先搞清楚这题到底在数什么
动手写代码之前，把问题模型想清楚比什么都重要。这个题表面上是一个数组分割问题，本质上是一个“合法分裂点计数问题”。我一开始也犯过迷糊，以为 DP 是要把数组拆成一段段最优子结构，但实际它的计数方式更微妙——我们数的不是子数组本身，而是“一对满足条件的分割点 (i, j)”。
1.1 第一版解法的痛点：枚举太贵
先回顾一下暴力思路，方便后面对比。第一个分割点 i 把数组分成[0, i)和[i, n)，第二个分割点 j 再把后半部分切成[i, j)和[j, n)。要保证第二段和第三段非空，所以 i 和 j 的枚举范围分别是1 到 n-2和i+1 到 n-1。每枚举一组，都要对三段分别做一次区间求和判断。
如果用前缀和预计算，每次区间求和是 O(1)，但两层循环还是要 O(n²)。我实际测过，n=5000 时大概几十毫秒，n=50000 开始吃力，n=10⁵ 级别就直接超时。关键问题是，j 移动一格时，第二段[i, j)的区间和只变化了一个元素，但暴力做法会把它从头算一遍，完全浪费了之前计算的结果。
1.2 解法二为什么必须用 DP
解法二的思路核心是：不要枚举“每一对”分割点，而是把“第二段右边界 j 移动”这件事当成一个递推过程。当 j 从某个位置往右走一步时，新的合法第二段集合只比原来多了一个候选起点，同时可能因为区间和变大而淘汰掉一些旧候选起点。维护这个“合法起点集合”的增减，就能在 j 的过程中实时知道当前有多少个 i 可以让第二段合法，然后一次性累加到答案里。
这其实就是 DP 里的“状态复用”，跟背包问题里反复强调的“不要重复计算子问题”是同一个道理。我这里把 DP 语义定义成：dp[j]表示以 j 作为第二段右边界时，前面能够凑出合法前两段的方案数。这个定义的好处是递推时只需要关心 j 的变化，不需要回头重新枚举 i。
1.3 用排队例子理解三段分割计数
为了不对 DP 术语发怵，我用一个场景帮助理解。想象一条队伍，要找一个地方设两个栅栏，把队伍分成三个区，每个区的人数权重总和不能超过上限。第一个栅栏的位置 i 设好以后，第二个栅栏从左往右慢慢挪。每挪一步，左边就多一个人，第二区变重了；如果第二区超重，就把第一个栅栏也往右挪，直到第二区重新变“合法”。整个过程里，第一个栅栏的位置只会往右走，不会回头。
这个“两个指针都只往右走”的性质，就是 O(n) 解法的灵魂所在。它对应到代码里就是滑动窗口：j 是窗口右边界，窗口里存放的是所有能让第二段合法的候选 i。只要 i 的取值范围是一个连续区间，并且随着 j 递增而单调右移，就可以用两个指针维护。
提示：理解这一点后，你会明白解法二的本质不是“复杂 DP”，而是“单调性优化下的状态计数”。
2. DP 解法核心：把枚举变成递推
前面铺垫了这么多，现在正式展开 DP 解法的推导过程。我按“状态定义 → 转移推导 → 边界处理”三步来走，每一步都说清楚为什么这么做。
2.1 状态定义与子结构拆解
设原数组长度为 n，下标从 0 开始。前缀和数组pref[i]表示nums[0..i-1]的和，那么区间[l, r)的和就是pref[r] - pref[l]。这套下标约定非常重要，后面所有代码都基于左闭右开区间，避免大量+1/-1带来的混乱。
定义两个辅助数组和一个 DP 数组：
left[i]：布尔数组，表示第一段[0, i)是否合法，即是否非空且区间和不超过 K。valid[i]：布尔数组，表示以 i 作为第一段终点时，第二段[i, j)在某个具体 j 下是否合法。这个数组其实是动态的，所以代码里我没有存成数组，而是用滑动窗口实时维护计数。dp[j]：以 j 作为第二段右边界时，满足“第一段合法 + 第二段合法”的方案数。
为什么状态里只记录第二段右边界，不把第一段终点也记录进去？这是因为第三段合法性的判断只依赖第二段右边界，不依赖第一段终点。换句话说，所有不同的 i 只要第二段右边界相同，它们对后续答案的贡献是完全等价的。这个“等价合并”就是 DP 能压缩状态数量的关键。
2.2 递推过程中窗口如何维护
现在看 j 从 2 递增到 n-1 的过程（j 至少为 2，是因为第一段和第二段都非空，最少各占一个元素）。
当第二段右边界从 j-1 移动到 j 时，第二段[i, j)比原来多包含了nums[j-1]这个元素，区间和变大。原本合法的 i 可能变得不合法，但同时会新增一个候选起点i = j-1，因为第二段新增了一种最短切法。这个新增起点是否计入，要看left[j-1]是否合法，以及第二段[j-1, j)本身和是否不超过 K。
候选合法 i 的集合会始终呈现一个连续区间的形态，因为数组元素全是非负的话（题目保证非负是前提），i 越小，第二段区间越长、和越大，越容易超过 K；i 越大，第二段区间越短、和越小，越容易合法。因此，当 j 变大时，我们只需要把左指针往右移动，把那些因为第二段超重而失效的 i 踢出窗口，再在右端加入新增的候选 i，就可以维持整个窗口的合法性。
用生活类比再看一遍：餐厅里有一个不断变长的取餐队伍，每来一个新顾客拿餐，窗口就变重一点。负荷太重的窗口就得从最前面放走几个顾客，直到整个窗口符合承载上限。我们关心的不是具体哪几个顾客，而是“窗口里当前有多少个顾客”这个总数。
2.3 边界条件与初值设定
写代码之前最容易错的就是边界。第一个分割点 i 最小是 1，最大是 n-2，因为第二段和第三段都要非空。第二个分割点 j 最小是 2，最大是 n-1。代码里循环我写成for j in range(2, n)，对应 j 的取值 2 到 n-1；第三段区间[j, n)在 j=n-1 时只有一个元素，依然非空。
窗口左指针left_ptr初始为 1。现在我把窗口里的候选起点理解成“所有满足 left[i] 为真，并且当前第二段和不超过 K 的 i”。当 j=2 时，第二段只有一种可能形态[1, 2)，也就是nums[1]一个元素。这时检查left[1]是否为真，以及nums[1]是否不超过 K，决定窗口计数是 0 还是 1。
有一个很隐蔽的细节：窗口收缩时，不能只看left[i]为真就减计数。因为窗口里维护的计数是所有“曾经可用的 i”的数量，它必须和窗口的实际内容保持一致。我个人的习惯是把“新增候选”和“淘汰旧候选”拆成两个独立步骤，先加后减，避免同一个 i 被重复处理。
注意：前缀和数组长度是 n+1，因为
pref[0]=0，而pref[n]表示整个数组的和。用pref[j] - pref[i]求[i, j)和时，务必保证 i、j 都是前缀和数组的下标，而不是 nums 的下标。
3. 代码实现与逐行讲解
理论推导做完，直接给代码。我用 Python 写了解法二，并用几个随机数据跟暴力解法做了对拍，保证逻辑一致。
3.1 解法二完整代码
def count_valid_splits(nums, limit): n = len(nums) if n < 3: return 0 pref = [0] * (n + 1) for idx, val in enumerate(nums): pref[idx + 1] = pref[idx] + val def range_sum(l, r): # 左闭右开区间 [l, r) return pref[r] - pref[l] left = [False] * n # left[i] 表示第一段 [0, i) 是否合法 for i in range(1, n - 1): if range_sum(0, i) <= limit: left[i] = True ans = 0 cnt = 0 l = 1 # 窗口左边界，即候选第一段终点的最小值 for j in range(2, n): # 1. 新增候选：i = j - 1 if left[j - 1] and range_sum(j - 1, j) <= limit: cnt += 1 # 2. 窗口收缩：把超重的旧候选移出窗口 while l < j and range_sum(l, j) > limit: if left[l]: cnt -= 1 l += 1 # 3. 第三段合法时，累加当前窗口计数 if range_sum(j, n) <= limit: ans += cnt return ans代码主体只有三块，加起来不到三十行。第一步和第二步顺序很重要，我解释一下为什么必须先加后减：如果先收缩窗口，新增候选 i = j-1 可能落在收缩之后的范围内，也可能因为 l 移动超过了它，导致这个新候选被错误丢弃。先加入再收缩，就能保证新候选不会因为窗口右移而被跳过。
3.2 枚举顺序为什么是“同步渐进”
这个解法没有显式的二层循环，核心的递推全部集中在 j 循环内。每次 j 递增时，只做两件常数级操作：把 j-1 作为新候选尝试加入，再把 l 往右移动直到窗口合法。因为 l 在循环过程中只会单调递增，整个 while 循环的次数总和是 O(n)，所以总复杂度严格 O(n)。
相比之下，暴力解法里 j 每次移动时都要重新检查所有可能的 i，从 1 到 j-1 全部扫一遍，累计就是 O(n²)。这个差别在大数组下几乎是天壤之别。我自己用 n=100000、随机数组、K=某个中间阈值测过：暴力解法跑了大概 12 秒，解法二 0.02 秒不到，差距肉眼可见。
3.3 关键边界用一个测试用例验证
我拿一个非常容易出错的用例解释下标逻辑。假设数组是[1, 2, 3, 4, 5]，K=6。n=5，left 数组只关心 i=1、2、3：
left[1]：第一段[0,1)={1}，和 1 <= 6，合法。left[2]：第一段[0,2)={1,2}，和 3 <= 6，合法。left[3]：第一段[0,3)={1,2,3}，和 6 <= 6，合法。
手动模拟 j 从 2 到 4：
- j=2，新增 i=1，
left[1]为真，第二段[1,2)={2}和 2<=6，cnt=1；窗口不用收缩；第三段[2,5)={3,4,5}和 12>6，不累加。 - j=3，新增 i=2，
left[2]为真，第二段[2,3)={3}和 3<=6，cnt=2；窗口收缩检查range_sum(1,3)=2+3=5<=6，不收缩；第三段[3,5)={4,5}和 9>6，不累加。 - j=4，新增 i=3，
left[3]为真，第二段[3,4)={4}和 4<=6，cnt=3；窗口收缩检查range_sum(1,4)=2+3+4=9>6，所以把 i=1 移出，cnt=2，l 变为 2；再检查range_sum(2,4)=3+4=7>6，移出 i=2，cnt=1，l 变为 3；第三段[4,5)={5}和 5<=6，累加 ans=1。
所以最终答案是 1，对应i=3, j=4的切法：[1,2,3] | [4] | [5]。这个用例同时验证了窗口收缩逻辑和第三段判断逻辑，非常推荐自己手跑一遍找感觉。
提示：写完代码后用随机小数组和暴力解对拍几次，确认没问题再提交。对拍脚本很简单，暴力两层循环加前缀和，随机生成一千组数据对比结果。
4. 实战中的常见坑与排查思路
DP 解法代码短，但容易出错的细节一点都不少。这一节我把实际跑题过程中遇到过的坑全部列出来，并给出排查建议。这些问题在网上题解区反复出现，属于“看着简单其实很容易翻车”的高发区域。
4.1 前缀和溢出与类型选择
前缀和数组存的是整个区间的累加和。如果 nums 元素本身很大，比如单个元素接近 10⁹，数组长度又达到 10⁵，前缀和最大值能到 10¹⁴ 级别。Python 的 int 是任意精度，不用操心；如果换用 C++ 或 Java，一定要用 long 而不是 int。我之前在本地用 C++ 测试时，一时偷懒写了vector<int>，结果求和直接溢出变成负数，窗口收缩逻辑被完全破坏，答案怎么都不对。排查办法很简单：打印最大前缀和，看是否超过 int 上限 2.1×10⁹，超了就换类型。
4.2 左闭右开区间与下标偏移混乱
这是我见过最多人翻车的地方。前缀和pref[i]表示前 i 个元素的和，区间[l, r)对应pref[r] - pref[l]。判断第一段[0, i)时，用的是pref[i] - pref[0]，也就是pref[i]。判断第二段[i, j)时，用的是pref[j] - pref[i]。判断第三段[j, n)时，用的是pref[n] - pref[j]。
如果你一会儿用闭区间一会儿用半开区间，很容易出现“差一个元素”的错误。我的建议是全程只写左闭右开，并且所有下标都用“前缀和数组下标”来理解，而不是“nums 中元素的位置”。这样虽然初学有点别扭，但写完以后几乎不会出现 off-by-one 错误。
4.3 窗口收缩时计数没同步更新
这个 bug 非常隐蔽，因为不仔细看很难发现。当range_sum(l, j)超过 limit 时，l 需要右移，但右移前必须检查left[l]是否为真。如果为真，说明这个候选之前被计入了窗口计数 cnt，现在移出必须减一；如果为假，说明它从来就没被计入，不能多减。我见过有人不加判断直接cnt -= 1，结果 cnt 变成负数，最终答案完全错乱。
另一个相关错误是：收缩时只移出了 l，但 l 可能已经越过了新增候选 j-1。前面提到必须先加新候选再收缩，就是为了避免这种情况。如果你发现答案偏小，优先怀疑这里的顺序问题。
4.4 单调性失效的场景要提前识别
解法二的核心依赖是“数组元素非负”。只要元素非负，第二段区间和随 l 的增大而减小，窗口收缩才有单调性。如果数组里有负数，窗口里合法 i 的集合就不一定是连续区间，滑动窗口会漏计，解法二直接不可用。碰到有负数的变体，得改用其他思路，比如对每个 j 用二分找到合法 i 的范围，前提是前缀和具备单调性；如果前缀和也不单调，那就只能回到带预处理的 O(n²) 或线段树维护，复杂度会显著上升。
我在刷题时习惯先确认题面里有没有“非负整数”这几个字，看到才决定是否套滑动窗口。没有的话，这个解法二就要谨慎使用或改写。
5. 从这道题能延伸出去的套路
刷题不能只盯着一道题。这个“三段式数组 II”背后的模型非常通用，拓展开可以解决一批类似的“计数合法分割点”问题。把套路抽出来，以后遇到新题能一眼看穿结构。
5.1 “合法分裂点计数”问题模型
这类题目通常有共同特征：一个长度为 n 的数组，用 k 个分割点分成 k+1 段，每段都要满足某个性质，统计满足条件的分割方案数。暴力枚举所有分割点是 C(n, k) 级别，但一旦 segment 的合格条件满足单调性，就可以用“DP 叠加滑窗”把复杂度降到 O(n)。
核心建模步骤归纳成三步：
- 用前缀和把区间信息压缩成常数时间查询。
- 定义 DP 状态，只记录“最后一段右边界”，把前面所有可行切法合并成一个计数。
- 维护一个从左往右滑动的候选集合，随边界递增动态增删，保证每次查询候选集合法值都是 O(1)。
这个套路不仅适用于“和不超过 K”，也适用于“段内最大值不超过 K”（配合单调队列而不是简单滑窗）、“段内元素互不相同”（配合哈希表维护），核心思路完全一致。
5.2 三道可以拿来练手的同类题
我刷题时喜欢把同类型的题放在一起做，对比它们的状态定义和滑动窗口差异。这里列三个我练过且觉得对理解这题有帮助的题目类型：
- 第一类：将数组分成 k 段，使每段和都不超过某个值，求方案数。比本题更泛化，充分理解本题后，可以尝试把 k 从 2 扩展到 3、4，感受状态维度变多后如何推广。
- 第二类：给定一个数组，问有多少个子数组满足某种条件，维护窗口计数。这题不像三段式那样有全局切分，但滑动窗口增删计数的写法几乎一模一样，可以作为基础练习。
- 第三类：统计所有“i < j 且同时满足条件 A(i) 和 B(j)”的点对数。这类题常把第一条件预处理成一个数组，再在遍历 j 时维护第二个条件的计数，结构跟本题的 left 数组 + cnt 累加如出一辙。
每道题做完，我会在笔记里画一张“状态维度 → 候选集合 → 增减方式”的小表格，横向对比后记忆会牢固很多。这个方法同样推荐给你，效果好过题海战术。
5.3 我的刷题习惯：先暴力后优化
这道题我是先写了暴力解法，再写 DP 解法的。很多人刷题时急于看题解、抄最优解，但我觉得先写一个能 AC 的暴力版本特别有价值——它能帮你验证题意的理解是否正确，也能在写 DP 时用来对拍。以这题为例，暴力版本大概十五行，跑通以后作为参照，每写一步 DP 就随机生成十组小数据对拍，几乎能定位所有逻辑错误。
等 DP 版本对拍通过，再把它提交到评测环境验证性能。这种“暴力保底、优化为主、对拍兜底”的流程，是我个人刷算法题最推荐的方式，既能保证正确性，又能逼自己真正理解优化点在哪里，而不是背模板式地抄代码。
复盘这道题需要注意的经验
如果只让我留一条建议，那就是：写这类计数题之前，先把“状态里合并了什么、边界条件是什么”想明白再动手。本题最容易出错的地方不是 DP 转移本身，而是窗口收缩时计数没有和候选集合保持同步。所以代码写完以后，一定要用一个多候选、多收缩的用例手跑一遍，比如我前面举的[1,2,3,4,5]这个例子，它能在三十秒内暴露绝大多数实现错误。
另外，如果时间允许，建议把这个解法和暴力解法都保留下来。以后遇到解法二思路失效的变体题，暴力版本可以直接改造成调试工具，帮你快速定位是新加的约束影响了单调性，还是单纯的边界写错了。这种双版本并存的做法，对我实际刷题帮助非常大，你可以试试。
