当前位置：首页 > news >正文

划分dp

news 2026/5/12 10:29:59

3578. 统计极差最大为 K 的分割方式数 - 力扣（LeetCode）

class Solution {
public:int countPartitions(vector<int>& nums, int k) {static constexpr int MOD = 1e9 + 7;int n = nums.size();deque<int> max_q, min_q;int left = 0;vector<int> dp(n + 1);dp[0] = 1;long long sum_dp = 0;for (int i = 0; i < n; i++){int x = nums[i];sum_dp += dp[i];// 保证max_q.front()是最大值while (!max_q.empty() && nums[max_q.back()] <= x){max_q.pop_back();}max_q.push_back(i);// 保证min_q.front()是最小值while (!min_q.empty() && nums[min_q.back()] >= x){min_q.pop_back();}min_q.push_back(i);while (nums[max_q.front()] - nums[min_q.front()] > k){sum_dp -= dp[left];left++;if (max_q.front() < left) max_q.pop_front();if (min_q.front() < left) min_q.pop_front();}dp[i + 1] = sum_dp % MOD;}return dp[n];}
};

1. 核心逻辑：枚举“最后一段”在哪里切

假设我们现在要把整个数组（或者数组的前几项）切分完毕。无论前面切了多少刀，必然存在最后一段（Last Partition）。

假设我们正在计算 f[i+1]（即前 i+1 个数字的划分方案总数），当前的末尾元素是 nums[i]。

这“最后一段”必须以 nums[i] 结尾。那么这一段的起点在哪里呢？假设最后一段的起点是 j（left <= j <= i），那么最后一段就是 nums[j...i]。

如果最后一段 nums[j...i] 是合法的（极差 ≤k）；
那么，这一种切分方案的总数，就等于“切掉这最后一段后，剩下前面 j 个元素的划分方案数”。
前面 j 个元素的划分方案数，正是我们在之前已经算出来的 f[j]。

2. 为什么是求和 (Sum)？

对于当前的结尾 i，最后一段的起点 j 可能有很多种选择。

起点可以是 i 自己（最后一段只有一个数 [nums[i]]），对应方案数 f[i]。
起点可以是 i-1（最后一段是 [nums[i-1], nums[i]]），对应方案数 f[i-1]。
...
起点最远可以是 left（最后一段是 [nums[left]...nums[i]]），对应方案数 f[left]。

根据组合数学的加法原理：

如果完成一件事（划分前 i+1 个数）有 N 类互不重叠的方法（由最后一段的起点 j 不同来分类），那么总方法数等于每一类方法数之和。

所以： $$ f[i+1] = f[left] + f[left+1] + ... + f[i] $$

这就解释了为什么我们需要维护 sum_f。

3. 图解演示

假设 nums = [A, B, C, D]，现在算到了 D (索引 i=3)。假设合法的 left 是 1 (对应元素 B)。这意味着：

[B, C, D] 是合法的。
[C, D] 是合法的。
[D] 是合法的。
但是 [A, B, C, D] 不合法（极差太大）。

那么以 D 结尾的划分方案由以下几种情况组成：

情况 1：最后一段是 [B, C, D]
- 那么前面剩下的就是 [A]。
- 方案数 = f[1]（[A] 的划分方案数）。
情况 2：最后一段是 [C, D]
- 那么前面剩下的就是 [A, B]。
- 方案数 = f[2]（[A, B] 的划分方案数）。
情况 3：最后一段是 [D]
- 那么前面剩下的就是 [A, B, C]。
- 方案数 = f[3]（[A, B, C] 的划分方案数）。

总方案数 f[4] = f[1] + f[2] + f[3]。

这就完美对应了代码中的逻辑： sum_f 维护的就是 f[left] ... f[i] 的和。

4. 代码中的接力棒

代码通过滑动窗口保证了数学上的正确性：

sum_f += f[i]:
- 刚进入循环时，我们把 f[i] 加入和。这代表假设最后一段长度为 1（只有 nums[i] 自己），那么它前面的方案数就是 f[i]。这是合法的候选者之一。
sum_f -= f[left] (在 while 循环中):
- 如果 nums[left...i] 的极差超过了 k，说明 left 不能作为最后一段的起点了。
- 既然 left 不能做起点，那么“前面剩下 left 个元素”这种切分情况就不成立了。
- 所以必须把 f[left] 从总和里减掉。
f[i+1] = sum_f:
- 经过筛选，sum_f 里剩下的就是所有合法起点的方案数之和。这就是到达当前这一步的总方案数。