线性动态规划：最长等差数列

题目描述
给定一个整数数组 nums，返回数组中最长等差数列的长度。数组中等差数列的定义是：至少包含 3 个元素，且任意两个相邻元素的差相等。数组元素的顺序不能改变。

示例：

• 输入：nums = [3,6,9,12]
  输出：4
  解释：整个数组就是公差为 3 的等差数列。
• 输入：nums = [9,4,7,2,10]
  输出：3
  解释：最长的等差数列是 [4,7,10] 或 [9,7,5]（但 5 不在数组中，实际是 [9,7,5] 不成立，正确应为 [4,7,10] 公差为 3）。

解题思路
本题的关键是：等差数列可以由任意两个元素确定一个公差。如果我们枚举所有可能的公差，并记录以某个位置结尾的等差数列长度，就能用动态规划解决。

步骤 1：定义状态
设 dp[i][d] 表示以 nums[i] 结尾、公差为 d 的等差数列的最大长度。但由于公差可能很大，我们通常用哈希表来存储公差：

• 定义 dp[i] 为一个哈希表，键是公差 d，值是以 nums[i] 结尾、公差为 d 的等差数列长度。

步骤 2：状态转移
对于每个 i（从 0 到 n-1），遍历所有 j（从 0 到 i-1）：

1. 计算公差 d = nums[i] - nums[j]。
2. 如果 dp[j] 中存在公差 d，说明在 j 之前已经有以 d 为公差的数列，那么接上 nums[i] 后长度加 1：
   dp[i][d] = dp[j][d] + 1
3. 如果 dp[j] 中没有公差 d，说明 nums[j] 和 nums[i] 是这个等差数列的前两项，此时长度为 2（但题目要求至少 3 个元素，所以长度为 2 时不更新答案）。

步骤 3：初始化
每个单独的元素可以视为任何公差的等差数列（长度为 1），但初始时所有 dp[i] 的哈希表为空。

步骤 4：记录答案
在遍历过程中，记录所有 dp[i][d] 的最大值，最终返回这个最大值（如果最大值小于 3，则返回 0，但题目通常保证至少有一个答案）。

详细推导（以 nums = [9,4,7,2,10] 为例）

1. i=0：dp[0] 为空（只有一个元素，无法构成等差数列）。
2. i=1：
   • j=0：d = 4-9 = -5，dp[1][-5] = 2（因为 dp[0] 没有 -5，所以初始为 2）。
3. i=2：
   • j=0：d = 7-9 = -2，dp[2][-2] = 2。
   • j=1：d = 7-4 = 3，dp[2][3] = 2。
4. i=3：
   • j=0：d = 2-9 = -7，dp[3][-7] = 2。
   • j=1：d = 2-4 = -2，此时 dp[1] 没有 -2，所以 dp[3][-2] = 2。
   • j=2：d = 2-7 = -5，此时 dp[2] 没有 -5，所以 dp[3][-5] = 2。
5. i=4：
   • j=0：d = 10-9 = 1，dp[4][1] = 2。
   • j=1：d = 10-4 = 6，dp[4][6] = 2。
   • j=2：d = 10-7 = 3，关键点：dp[2] 中有公差 3（对应数列 [4,7]），所以 dp[4][3] = dp[2][3] + 1 = 3，此时数列为 [4,7,10]。
   • j=3：d = 10-2 = 8，dp[4][8] = 2。

最终最大值为 3。

复杂度优化
直接使用二维哈希表可能会占用较大空间，但由于每个 dp[i] 只依赖于前面的 dp[j]，空间复杂度为 O(n²)（最坏情况公差不同），时间复杂度也是 O(n²)。

代码框架（伪代码）

def longestArithSeqLength(nums):
    n = len(nums)
    dp = [dict() for _ in range(n)]
    ans = 2  # 至少两个元素才能开始
    for i in range(n):
        for j in range(i):
            d = nums[i] - nums[j]
            if d in dp[j]:
                dp[i][d] = dp[j][d] + 1
            else:
                dp[i][d] = 2
            ans = max(ans, dp[i][d])
    return ans

总结
本题通过“结尾元素 + 公差”确定状态，利用哈希表避免枚举所有可能的公差，是线性动态规划中灵活使用数据结构的典型例子。