题目：线性动态规划：等差数列划分（Arithmetic Slices）

字数 3144 2025-12-23 18:55:51

好的，我注意到你的已讲题目列表非常详尽，涵盖了线性DP的众多经典和变种问题。为了避免重复，我将为你讲解一个有趣且有一定技巧性，但你的列表中似乎没有明确出现的题目：

题目：线性动态规划：等差数列划分（Arithmetic Slices）

题目描述

给定一个整数数组 nums，返回数组 子数组（是连续的）中，包含至少三个元素，且是一个“等差数列”的子数组的数量。

等差数列 的定义：如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

示例 1：
输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4]、[1, 2, 3, 4]。

示例 2：
输入：nums = [1]
输出：0
解释：没有包含至少三个元素的子数组。

解题思路：循序渐进

我们目标是统计所有长度 ≥ 3 的连续等差子数组的数量。核心在于如何高效地识别和统计这些“切片”。

第一步：理解基本模式

一个长度为 L 的连续等差子数组，能拆分成多少个符合条件（长度 ≥ 3）的“切片”呢？

长度为 3 的子数组：有 L - 2 个。
长度为 4 的子数组：有 L - 3 个。
...
长度为 L 的子数组：有 1 个。

所以，对于一个连续的等差段，其贡献的“切片”总数是：
(L-2) + (L-3) + ... + 1 = (L-2)(L-1) / 2

例如，[1,2,3,4] 长度 L=4，贡献 (4-2)(4-1)/2 = 3 个切片。

结论：如果我们能找到数组中所有最长的连续等差段，并对每个段计算上述公式，再求和，就能得到答案。

第二步：如何识别连续的等差段？——引入 dp[i] 状态

我们可以定义一个状态 dp[i]：

dp[i] 表示 以第 i 个元素（nums[i]）结尾的、并且长度 ≥ 2 的连续等差子数组的“增量长度”。
更通俗地讲，dp[i] 表示从某个起点到 i，连续满足等差的有效长度（以能形成的新切片数来衡量）。但标准定义更直接：
- dp[i] = 以 nums[i] 结尾的连续等差数列的最大长度（单位是“满足等差的三元组增量数”）。
- 状态转移方程：
  - 如果 nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，说明当前元素 i 和前面两个元素构成了一个新的、更长的等差连续段。那么，以 i 结尾的新增“切片”数量，比以 i-1 结尾的要多 1。
  - 即 dp[i] = dp[i-1] + 1。
  - 否则，当前元素破坏了等差连续性，那么以 i 结尾的新增“切片”数量为 0。即 dp[i] = 0。
初始化：
- 我们需要从索引 2 开始计算（因为至少需要三个元素）。
- dp[0] 和 dp[1] 可以初始化为 0，因为无法形成长度≥3的切片。

第三步：从 dp[i] 推导最终答案

这里 dp[i] 的定义非常巧妙。dp[i] 的实际含义是：当我们在位置 i 发现一个新的等差元素时，相比于位置 i-1，额外新增了多少个以 nums[i] 为结尾的等差切片。

让我们用例子 [1,2,3,4] 来验证：

索引从 0 开始。
i=2：nums[2]-nums[1] == nums[1]-nums[0] (3-2 == 2-1)。成立。dp[2] = dp[1] + 1 = 0 + 1 = 1。这个 1 代表以索引 2 结尾的新增切片：[1,2,3]。
i=3：nums[3]-nums[2] == nums[2]-nums[1] (4-3 == 3-2)。成立。dp[3] = dp[2] + 1 = 1 + 1 = 2。
这个 2 代表什么？
- 它表示以索引 3 结尾的新增切片有 2 个：
  1. 从索引 1 开始的新切片：[2,3,4]。
  2. 从索引 0 开始的更长的切片：[1,2,3,4]（这个切片包含了之前的 [1,2,3]，但 [1,2,3,4] 是长度≥3的另一个独立切片）。

最终答案 就是所有 dp[i] 的累加和。因为每个 dp[i] 都精确地计算了以 i 结尾的新增切片数，把它们全部加起来，就得到了整个数组的所有等差切片总数。

第四步：算法步骤（伪代码）

如果数组长度 n < 3，直接返回 0。
初始化一个长度 n 的数组 dp，所有元素为 0。
初始化变量 total = 0 用于累加答案。
从 i = 2 开始遍历到 n-1：
- 检查 nums[i] - nums[i-1] == nums[i-1] - nums[i-2]：
  - 如果成立：dp[i] = dp[i-1] + 1
  - 否则：dp[i] = 0
- total += dp[i]
返回 total。

第五步：空间优化

观察状态转移方程：dp[i] 只依赖于 dp[i-1]。我们不需要保存整个 dp 数组，只需要一个变量 current 来记录上一个 dp[i-1] 的值即可。

优化后的步骤：

如果 n < 3，返回 0。
初始化 total = 0， current = 0（代表 dp[i-1] 的初始值）。
从 i = 2 到 n-1：
- 如果 nums[i] - nums[i-1] == nums[i-1] - nums[i-2]：
  - current = current + 1
  - total += current
- 否则：
  - current = 0
返回 total。

第六步：举例验证（nums = [1,2,3,4,5]）

n=5 ≥ 3，继续。
total=0, current=0。
i=2: 3-2 == 2-1？是。current=0+1=1, total=0+1=1。 (新增切片: [1,2,3])
i=3: 4-3 == 3-2？是。current=1+1=2, total=1+2=3。(新增切片: [2,3,4], [1,2,3,4])
i=4: 5-4 == 4-3？是。current=2+1=3, total=3+3=6。(新增切片: [3,4,5], [2,3,4,5], [1,2,3,4,5])
最终 total = 6。
手动验证：长度为3的切片有3个([1,2,3],[2,3,4],[3,4,5])，长度为4的切片有2个([1,2,3,4],[2,3,4,5])，长度为5的切片有1个([1,2,3,4,5])，总计 3+2+1=6。结果正确。

总结

这道 “等差数列划分” 题目是线性动态规划的一个典型应用。其核心技巧在于：

状态定义：dp[i] 定义为以 nums[i] 结尾的新增等差切片数量。
状态转移：基于相邻差值的相等性，决定了当前状态是延续并增加（dp[i]=dp[i-1]+1）还是重置（dp[i]=0）。
结果累计：最终答案就是所有 dp[i] 的累加和，因为每个 dp[i] 都代表了以该位置结尾的、新的、有效的等差切片。

通过这个定义，我们巧妙地避免了复杂的组合计算，用 O(n) 的时间和 O(1) 的空间优雅地解决了问题。它体现了动态规划中“利用历史信息，定义增量贡献”的重要思想。

好的，我注意到你的已讲题目列表非常详尽，涵盖了线性DP的众多经典和变种问题。为了避免重复，我将为你讲解一个有趣且有一定技巧性，但你的列表中似乎没有明确出现的题目：题目：线性动态规划：等差数列划分（Arithmetic Slices）题目描述给定一个整数数组 nums ，返回数组子数组（是连续的）中，包含至少三个元素，且是一个“等差数列”的子数组的数量。等差数列的定义：如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。示例 1：输入： nums = [1,2,3,4] 输出： 3 解释：nums 中有三个子等差数组：[ 1, 2, 3]、[ 2, 3, 4]、[ 1, 2, 3, 4 ]。示例 2：输入： nums = [1] 输出： 0 解释：没有包含至少三个元素的子数组。解题思路：循序渐进我们目标是统计所有长度 ≥ 3 的连续等差子数组的数量。核心在于如何高效地识别和统计这些“切片”。第一步：理解基本模式一个长度为 L 的连续等差子数组，能拆分成多少个符合条件（长度 ≥ 3）的“切片”呢？长度为 3 的子数组：有 L - 2 个。长度为 4 的子数组：有 L - 3 个。 ... 长度为 L 的子数组：有 1 个。所以，对于一个连续的等差段，其贡献的“切片”总数是： (L-2) + (L-3) + ... + 1 = (L-2)(L-1) / 2 例如， [1,2,3,4] 长度 L=4，贡献 (4-2)(4-1)/2 = 3 个切片。结论：如果我们能找到数组中所有最长的连续等差段，并对每个段计算上述公式，再求和，就能得到答案。第二步：如何识别连续的等差段？——引入 dp[ i] 状态我们可以定义一个状态 dp[i] ： dp[i] 表示以第 i 个元素（nums[ i]）结尾的、并且长度 ≥ 2 的连续等差子数组的“增量长度” 。更通俗地讲， dp[i] 表示从某个起点到 i ，连续满足等差的有效长度（以能形成的新切片数来衡量）。但标准定义更直接： dp[i] = 以 nums[i] 结尾的连续等差数列的最大长度（单位是“满足等差的三元组增量数”）。状态转移方程：如果 nums[i] - nums[i-1] == nums[i-1] - nums[i-2] ，说明当前元素 i 和前面两个元素构成了一个新的、更长的等差连续段。那么，以 i 结尾的新增“切片”数量，比以 i-1 结尾的要多 1。即 dp[i] = dp[i-1] + 1 。否则，当前元素破坏了等差连续性，那么以 i 结尾的新增“切片”数量为 0。即 dp[i] = 0 。初始化：我们需要从索引 2 开始计算（因为至少需要三个元素）。 dp[0] 和 dp[1] 可以初始化为 0，因为无法形成长度≥3的切片。第三步：从 dp[ i] 推导最终答案这里 dp[i] 的定义非常巧妙。 dp[i] 的实际含义是：当我们在位置 i 发现一个新的等差元素时，相比于位置 i-1 ，额外新增了多少个以 nums[i] 为结尾的等差切片。让我们用例子 [1,2,3,4] 来验证：索引从 0 开始。 i=2 ： nums[2]-nums[1] == nums[1]-nums[0] (3-2 == 2-1)。成立。 dp[2] = dp[1] + 1 = 0 + 1 = 1 。这个 1 代表以索引 2 结尾的新增切片： [1,2,3] 。 i=3 ： nums[3]-nums[2] == nums[2]-nums[1] (4-3 == 3-2)。成立。 dp[3] = dp[2] + 1 = 1 + 1 = 2 。这个 2 代表什么？它表示以索引 3 结尾的新增切片有 2 个：从索引 1 开始的新切片： [2,3,4] 。从索引 0 开始的更长的切片： [1,2,3,4] （这个切片包含了之前的 [1,2,3] ，但 [1,2,3,4] 是长度≥3的另一个独立切片）。最终答案就是所有 dp[i] 的累加和。因为每个 dp[i] 都精确地计算了以 i 结尾的新增切片数，把它们全部加起来，就得到了整个数组的所有等差切片总数。第四步：算法步骤（伪代码）如果数组长度 n < 3 ，直接返回 0。初始化一个长度 n 的数组 dp ，所有元素为 0。初始化变量 total = 0 用于累加答案。从 i = 2 开始遍历到 n-1 ：检查 nums[i] - nums[i-1] == nums[i-1] - nums[i-2] ：如果成立： dp[i] = dp[i-1] + 1 否则： dp[i] = 0 total += dp[i] 返回 total 。第五步：空间优化观察状态转移方程： dp[i] 只依赖于 dp[i-1] 。我们不需要保存整个 dp 数组，只需要一个变量 current 来记录上一个 dp[i-1] 的值即可。优化后的步骤：如果 n < 3 ，返回 0。初始化 total = 0 ， current = 0 （代表 dp[i-1] 的初始值）。从 i = 2 到 n-1 ：如果 nums[i] - nums[i-1] == nums[i-1] - nums[i-2] ： current = current + 1 total += current 否则： current = 0 返回 total 。第六步：举例验证（nums = [ 1,2,3,4,5]） n=5 ≥ 3，继续。 total=0 , current=0 。 i=2 : 3-2 == 2-1？是。 current=0+1=1 , total=0+1=1 。 (新增切片: [ 1,2,3 ]) i=3 : 4-3 == 3-2？是。 current=1+1=2 , total=1+2=3 。(新增切片: [ 2,3,4], [ 1,2,3,4 ]) i=4 : 5-4 == 4-3？是。 current=2+1=3 , total=3+3=6 。(新增切片: [ 3,4,5], [ 2,3,4,5], [ 1,2,3,4,5 ]) 最终 total = 6 。手动验证：长度为3的切片有3个([ 1,2,3],[ 2,3,4],[ 3,4,5])，长度为4的切片有2个([ 1,2,3,4],[ 2,3,4,5])，长度为5的切片有1个([ 1,2,3,4,5 ])，总计 3+2+1=6。结果正确。总结这道 “等差数列划分” 题目是线性动态规划的一个典型应用。其核心技巧在于：状态定义： dp[i] 定义为以 nums[i] 结尾的新增等差切片数量。状态转移：基于相邻差值的相等性，决定了当前状态是延续并增加（ dp[i]=dp[i-1]+1 ）还是重置（ dp[i]=0 ）。结果累计：最终答案就是所有 dp[i] 的累加和，因为每个 dp[i] 都代表了以该位置结尾的、新的、有效的等差切片。通过这个定义，我们巧妙地避免了复杂的组合计算，用 O(n) 的时间和 O(1) 的空间优雅地解决了问题。它体现了动态规划中“利用历史信息，定义增量贡献”的重要思想。