线性动态规划：等差数列划分
题目描述
给定一个整数数组 nums，返回数组 nums 中所有为等差数列的连续子数组个数。
等差数列定义：一个数列中，任意相邻两项的差相等，这个固定的差称为公差。例如，[1, 3, 5, 7] 是公差为2的等差数列。
示例：
输入：nums = [1, 2, 3, 4]
输出：3
解释：nums 中有三个子数组是等差数列：
[1, 2, 3]
[2, 3, 4]
[1, 2, 3, 4]
注意：
- 子数组必须是连续的，且长度至少为3。
- 数组长度范围在
[1, 5000]之间，元素范围为[-1000, 1000]。
解题思路详解
1. 问题分析
我们需要统计数组中所有长度 ≥3 的连续等差数列子数组的个数。
一个直观的想法是，遍历所有可能的子数组，检查其是否为等差数列。但这样时间复杂度为 O(n³)，会超时（n 最大 5000）。
核心观察：
- 如果已知一个较长的等差数列，那么它的所有连续子段（长度 ≥3）也都是等差数列吗？
不一定！例如[1, 2, 3, 4]是等差数列，其子数组[2, 3, 4]也是，但更短的子数组如[1, 2, 3]也是。
实际上，一个长度为 L 的等差数列，包含的长度 ≥3 的连续子数组个数是(L-2) + (L-3) + ... + 1 = (L-1)(L-2)/2。
但直接按长度统计会重复计数，因为不同位置的等差数列会重叠。
更好的思路是动态规划，利用“以某个位置结尾的等差数列”这一状态，避免重复计算。
2. 动态规划定义状态
设 dp[i] 表示：以第 i 个元素结尾的、长度 ≥3 的连续等差数列的个数。
但这定义不方便直接递推，因为“长度 ≥3”这个条件在递推时需要特殊处理。
换个角度，定义：
diff[i] = nums[i] - nums[i-1] // 相邻两项的差
然后定义：
dp[i] = 以 nums[i] 结尾的、长度 ≥2 的连续等差数列的最大长度（即这个等差数列的元素个数）？
不，更好的定义是：
dp[i] = 以 nums[i] 结尾的、且与前一个元素 nums[i-1] 能构成等差数列的连续子数组的“等差增量计数”。
更准确的标准定义（来自经典的解法）：
dp[i] = 以 nums[i] 结尾的、长度至少为 3 的等差数列的个数。
但这样递推困难，因为需要知道前一个位置是否构成等差。
更常用且简单的状态定义：
设：
dp[i] = 以 nums[i] 结尾的连续等差数列的“潜在长度计数”，但我们需要长度至少为3时才计入答案。
实际上，更直接的方法是：
设 d[i] 表示以 nums[i] 结尾的、且公差为某个值的连续等差数列的“扩展计数”。
标准状态定义：
定义 dp[i] 为：以 nums[i] 结尾的、且与 nums[i-1] 的差等于整个等差数列的公差的连续等差数列的最大长度（即这个等差数列的元素个数）。
更具体地：
- 如果
nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，说明nums[i-2], nums[i-1], nums[i]能构成一个长度为 3 的等差数列，那么以 nums[i] 结尾的等差数列长度 = 以 nums[i-1] 结尾的等差数列长度 + 1。 - 否则，以 nums[i] 结尾的等差数列长度为 2（即只包含 nums[i-1] 和 nums[i]，但长度 2 不算有效等差数列）。
用公式表示：
设 diff = nums[i] - nums[i-1]
如果 diff == nums[i-1] - nums[i-2]（i ≥ 2），
则 dp[i] = dp[i-1] + 1
否则 dp[i] = 0
这里 dp[i] 的含义是：以 nums[i] 结尾的、且长度至少为 3 的等差数列的“新增数量”？
仔细看，dp[i] 实际上是“新增的等差数列个数”，但这个“新增”是指以 i 结尾的等差数列中，长度 ≥3 的那些。
更准确的理解（这是经典解法）：
定义 dp[i] 表示：以 nums[i] 结尾的、长度至少为 3 的等差数列的个数。
那么如何递推？
- 如果
nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，说明从 i-2 到 i 这三个数构成等差数列。
那么，所有以 i-1 结尾的长度 ≥3 的等差数列，在末尾加上 nums[i] 后，仍然构成等差数列，并且还新增了一个长度为 3 的等差数列（即 i-2, i-1, i 这三个数）。
所以dp[i] = dp[i-1] + 1。 - 否则，
dp[i] = 0。
例子：
nums = [1, 2, 3, 4]
i=2: nums[2]-nums[1]=1, nums[1]-nums[0]=1，相等，所以 dp[2] = dp[1] + 1 = 0 + 1 = 1，表示以 3 结尾的长度 ≥3 的等差数列有 1 个：[1,2,3]。
i=3: 4-3=1, 3-2=1，相等，dp[3] = dp[2] + 1 = 1 + 1 = 2，表示以 4 结尾的长度 ≥3 的等差数列有 2 个：[2,3,4] 和 [1,2,3,4]。
最后答案是 sum(dp[0..n-1])。
3. 状态转移方程
- 初始化：
dp[0] = 0, dp[1] = 0，因为长度至少为 3。 - 对于 i ≥ 2：
- 如果
nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，则dp[i] = dp[i-1] + 1 - 否则
dp[i] = 0
- 如果
- 结果 = Σ dp[i] （i 从 0 到 n-1）
为什么 dp[i] = dp[i-1] + 1？
因为当 i 能与前两个数构成等差数列时，所有以 i-1 结尾的长度 ≥3 的等差数列，在末尾添加 nums[i] 后仍然保持等差性质（公差不变），所以数量继承 dp[i-1]。
同时，新增了一个长度为 3 的等差数列 [i-2, i-1, i]，所以额外 +1。
4. 例子推导
nums = [1, 2, 3, 4, 5]
| i | nums[i] | diff = nums[i]-nums[i-1] | 与前一个 diff 相等？ | dp[i] | 解释 |
|---|---|---|---|---|---|
| 0 | 1 | - | - | 0 | 初始化 |
| 1 | 2 | 1 | - | 0 | 初始化 |
| 2 | 3 | 1 | 相等（i=2, diff=1, prev_diff=1） | 1 | 新增 [1,2,3] |
| 3 | 4 | 1 | 相等 | dp[2]+1=2 | 新增 [2,3,4] 和 [1,2,3,4] |
| 4 | 5 | 1 | 相等 | dp[3]+1=3 | 新增 [3,4,5], [2,3,4,5], [1,2,3,4,5] |
dp 数组 = [0, 0, 1, 2, 3]
总和 = 1+2+3 = 6。
验证：长度 ≥3 的等差数列子数组有：
- 长度3: [1,2,3], [2,3,4], [3,4,5] → 3个
- 长度4: [1,2,3,4], [2,3,4,5] → 2个
- 长度5: [1,2,3,4,5] → 1个
总数 3+2+1=6，与动态规划结果一致。
5. 算法步骤
- 如果数组长度 n < 3，直接返回 0。
- 初始化 dp 数组长度为 n，dp[0]=0, dp[1]=0。
- 初始化结果 total = 0。
- 从 i=2 到 n-1：
- 如果 nums[i] - nums[i-1] == nums[i-1] - nums[i-2]：
- dp[i] = dp[i-1] + 1
- total += dp[i]
- 否则：
- dp[i] = 0
- 如果 nums[i] - nums[i-1] == nums[i-1] - nums[i-2]：
- 返回 total。
实际上，dp[i] 只依赖于 dp[i-1]，所以可以用一个变量 current 代替 dp 数组，优化空间复杂度为 O(1)。
6. 优化空间复杂度
用变量 curr 表示当前的 dp[i]：
- 初始化
curr = 0,total = 0。 - 从 i=2 到 n-1：
- 如果满足等差条件，
curr = curr + 1，否则curr = 0。 total += curr。
- 如果满足等差条件，
最终代码（Python）：
def numberOfArithmeticSlices(nums):
n = len(nums)
if n < 3:
return 0
total = 0
curr = 0
for i in range(2, n):
if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
curr += 1
total += curr
else:
curr = 0
return total
时间复杂度：O(n)，只遍历一次数组。
空间复杂度：O(1)，只用了常数个变量。
总结
这个问题的动态规划思路是：
- 定义
dp[i]为以 nums[i] 结尾的长度 ≥3 的等差数列个数。 - 状态转移基于相邻三数的差是否相等，若相等则
dp[i] = dp[i-1] + 1。 - 最终答案是所有 dp[i] 的总和。
这个方法巧妙利用了“等差数列的扩展性质”，将问题转化为简单的线性 DP，且可以优化到 O(1) 空间。