线性动态规划：等差数列划分 II - 子序列 题目描述 给定一个整数数组 nums ，返回数组中所有为等差数列的 子序列 的个数。注意：子序列不要求连续，但必须保持原始顺序；等差数列至少包含3个元素，且公差相同（包括公差为0或负数）。例如， nums = [2,4,6,8,10] 的结果为7，因为包含的等差数列子序列有： [ 2,4,6 ] [ 2,4,6,8 ] [ 2,4,6,8,10 ] [ 2,6,10 ] [ 4,6,8 ] [ 4,6,8,10 ] [ 6,8,10 ] 解题过程 步骤1：理解问题本质 目标：统计所有长度≥3的等差数列子序列的数量。 难点：子序列不连续，且同一元素可能参与多个不同公差的等差数列。 关键思路：若已知以某对元素 (nums[i], nums[j]) 为末尾的、公差为 d 的等差子序列数量，则可通过动态规划递推。 步骤2：定义动态规划状态 令 dp[i][d] 表示以 nums[i] 结尾、公差为 d 的弱等差子序列（长度≥2）的个数。 注意：弱等差子序列包含长度为2的序列，方便后续扩展。 但公差 d 可能非常大，直接使用二维数组会内存爆炸。因此改用哈希表或字典结构： 定义 dp[i] 为一个字典，键是公差 d ，值是以 nums[i] 结尾、公差为 d 的弱等差子序列数量。 步骤3：状态转移方程 遍历所有 j < i ，计算公差 d = nums[i] - nums[j] 。 对于固定的 d ，以 nums[i] 结尾、公差为 d 的弱等差子序列可由两部分组成： 直接由 nums[j] 和 nums[i] 组成的长度为2的新序列。 在 nums[j] 结尾的公差为 d 的弱等差子序列后追加 nums[i] （这些序列长度≥2，追加后长度≥3）。 因此转移方程为： \[ dp[ i][ d] \ += \ dp[ j][ d ] + 1 \] 其中 dp[j][d] + 1 表示： dp[j][d] 是长度≥2的序列，追加 nums[i] 后得到长度≥3的等差子序列（这些会被计入答案），同时新增一个长度为2的序列 (nums[j], nums[i]) 。 步骤4：统计有效答案 在转移过程中，每当执行 dp[i][d] += dp[j][d] 时，实际上 dp[j][d] 表示以 nums[j] 结尾、公差为 d 的弱等差子序列数量（长度≥2），追加 nums[i] 后得到长度≥3的等差子序列，因此将 dp[j][d] 累加到答案 ans 中。 注意：直接加 dp[j][d] 而不是 dp[j][d] + 1 ，因为长度为2的序列追加后才是有效序列（长度≥3）。 步骤5：具体实现细节 使用一个列表 dp ，其中 dp[i] 是字典，记录以 i 结尾的各公差的弱等差子序列数量。 初始化：所有 dp[i] 为空字典。 遍历 i 从0到 n-1 ，对于每个 j < i ： 计算 d = nums[i] - nums[j] 。 获取 dp[j] 中公差 d 对应的值 cnt （若不存在则 cnt=0 ）。 将 cnt 加入答案 ans （因为 cnt 对应长度≥2的序列，追加 nums[i] 后长度≥3）。 更新 dp[i][d] += cnt + 1 。 步骤6：复杂度分析 时间复杂度：O(n²)，需要两重循环遍历所有 (i, j) 对。 空间复杂度：O(n²)，最坏情况下每个 dp[i] 可能存储 O(n) 个公差。 示例演示 以 nums = [2,4,6,8] 为例： i=2 （元素6）： j=1 （元素4）， d=2 ， dp[1] 中 d=2 的值为1（序列[ 2,4]），此时将1加入答案（得到序列[ 2,4,6]），并更新 dp[2][2] = 1 + 1 = 2 （包含[ 4,6]和[ 2,4,6]？不对，注意 dp[i][d] 记录的是以 i 结尾的弱等差序列数量，[ 2,4,6 ]是以6结尾但不会被重复计数，因为答案在追加时统计）。 逐步执行后可得总答案为7（与题目示例一致）。 通过以上步骤，即可高效统计所有长度≥3的等差数列子序列数目。