线性动态规划：等差数列划分 II - 子序列 题目描述 给定一个整数数组 nums ，返回数组中所有为等差序列的子序列个数。如果一个序列中至少有三个元素，并且任意两个相邻元素之差相同，则称其为等差序列。 例如，给定 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的等差子序列的数量。 关键难点：等差子序列不要求连续，因此需要动态规划记录以任意位置结尾的等差序列信息。 例如，对于序列 [2,4,6,8] ，以 8 结尾的等差序列可能依赖前面的 6 、 4 、 2 等元素。 步骤2：定义动态规划状态 设 dp[i][d] 表示以第 i 个元素结尾、公差为 d 的等差子序列的数量。 但公差 d 可能是任意整数（包括负数），直接使用二维数组会因 d 的范围过大而内存爆炸。 优化方案：使用哈希表数组， dp[i] 是一个哈希表，键为公差 d ，值为以 nums[i] 结尾、公差为 d 的等差子序列数量。 步骤3：状态转移方程 对于每个 i （当前元素），遍历所有 j < i （前面的元素）： 计算公差 d = nums[i] - nums[j] 。 以 nums[i] 结尾、公差为 d 的序列可由以下两部分组成： 长度为2的序列 ：直接由 nums[j] 和 nums[i] 组成，这类序列不计入答案（因为长度至少为3）。 长度≥3的序列 ：在 nums[j] 结尾的公差为 d 的序列后追加 nums[i] 。若 dp[j] 中存在键 d ，说明已有以 nums[j] 结尾的长度≥2的序列，追加后长度≥3，可计入答案。 因此，转移方程为： 若 dp[j] 中存在公差 d ，则 ans += dp[j][d] （这些序列追加 nums[i] 后长度≥3）。 更新 dp[i][d] += dp[j][d] + 1 ，其中 +1 表示新增的 [nums[j], nums[i]] 这个长度为2的序列。 步骤4：初始化与遍历顺序 初始化： dp[i] 均为空哈希表， ans = 0 。 遍历顺序：外层循环 i 从 0 到 n-1 ，内层循环 j 从 0 到 i-1 。 步骤5：示例演示 以 nums = [2,4,6,8] 为例： i=0 ： dp[0] 为空。 i=1 ： j=0 ， d=2 ， dp[0] 无键 2 ， ans 不变， dp[1][2] = 0 + 1 = 1 （序列 [2,4] ）。 i=2 ： j=0 ， d=4 ， dp[0] 无键 4 ， dp[2][4] = 0 + 1 = 1 （序列 [2,6] ）。 j=1 ， d=2 ， dp[1][2] = 1 ，说明存在 [2,4] ，追加 6 形成 [2,4,6] ， ans += 1 。 更新 dp[2][2] = 0 + 1 + 1 = 2 （新增 [4,6] ，并继承 [2,4,6] 的计数？注意：实际是累加 dp[1][2] + 1 ，即 1 + 1 = 2 ）。 i=3 ： j=0 ， d=6 ，无键， dp[3][6] = 1 （ [2,8] ）。 j=1 ， d=4 ， dp[1] 无键 4 ， dp[3][4] = 1 （ [4,8] ）。 j=2 ， d=2 ， dp[2][2] = 2 ，说明有2个序列以 6 结尾、公差为2： [4,6] 追加 8 得 [4,6,8] [2,4,6] 追加 8 得 [2,4,6,8] ans += 2 。 更新 dp[3][2] = 0 + 2 + 1 = 3 （新增 [6,8] ，并继承前两个序列的计数）。 最终 ans = 1 + 2 = 3 ，对应 [2,4,6] 、 [4,6,8] 、 [2,4,6,8] 。但题目示例中还有 [2,6,10] 等，需注意完整计算。 步骤6：复杂度分析 时间复杂度：O(n²)，因需双重循环。 空间复杂度：O(n²)，最坏情况下每个 dp[i] 可能存储 O(n) 个公差。 总结 本题通过哈希表记录以每个位置结尾的不同公差的序列数，巧妙地将不连续子序列问题转化为动态规划问题。关键点在于区分长度为2的序列（不计入答案但需记录）和长度≥3的序列（计入答案）。