本页为题单说明，测评请cout<<"ok"

查看教程pdf

题目： 最长等差子数列 (Longest Arithmetic Subsequence)

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。 回顾一下，nums 的子序列 $sub$ 是从 nums 删除一些元素（也可以不删除）得到的一个序列。如果 $sub[i+1] - sub[i]$ 的值对于所有 $0 \le i < sub.length - 1$ 都相等，那么这个子序列就是等差的。

资深教练的启发式笔记：从“单兵作战”到“寻找拍档”

孩子，当你习惯了用 dp[i] 表示“以 $i$ 结尾的最优解”时，你其实是在处理一种一元依赖（比如最长递增子序列，只要比前一个大就行）。但等差数列不同，它是一种三元约束：如果你只知道当前数和前一个数，你根本不知道“公差”是多少，也就无法判断能不能接上。

这就是我们要引入“维度升级”的原因。

核心知识点清单

1. 状态的升维（State Expansion）：

   • 启发： 既然一个人（当前数）定不了规则，两个人（当前数 + 前一个数）总能定出公差了吧？
   • 知识点： 定义 dp[i][diff] 为以索引 $i$ 结尾、公差为 diff 的子序列长度。

2. 公差的隐式处理（Implicit Difference）：

   • 启发： 不要去预设公差是多少。遍历 $i$ 之前的所有 $j$，每一个 $(j, i)$ 对都会碰撞出一个唯一的公差 $d = nums[i] - nums[j]$。
   • 知识点： 转移方程 $dp[i][d] = dp[j][d] + 1$。

3. 稀疏状态的管理（Sparse DP）：

   • 启发： 差值的范围可能很大（比如 $10^9$），直接开二维数组会炸空间，且大部分位置是空的。
   • 知识点： 使用 std::unordered_map 或哈希表向量 vector<unordered_map<int, int>> dp(n)，仅记录出现过的公差。

4. 类斐波那契的变形（Relation Transformation）：

   • 启发： 如果规则从 $A+D=B$ 变成 $A+B=C$（斐波那契类），逻辑变了吗？没变，依然是“找前两个”。
   • 知识点： 建立“值到索引”的映射 val_to_index，通过 $nums[i] - nums[j]$ 快速锁定前驱索引 $k$。

5. 工程陷阱（Common Pitfalls）：

   • 基准长度： 任何两个数都能组成等差数列，所以基础长度是 2，不是 1。
   • 全局更新： 答案不一定在 dp[n-1]，每算出一个状态都要尝试更新 ans。

洛谷对应练习推荐

为了巩固这些启发式思维，请按顺序挑战以下题目：

1. 等差子序列 DP 进阶：

   P4933 大师 （注：此题要求统计等差子序列的个数，但其状态转移逻辑 $dp[i][diff]$ 与资料中求最长长度完全一致，是掌握该模板的最佳题目。）

2. 三元关系基础（上升三元组）：

   P1637 三元上升子序列 （理解“当前元素依赖于前一个、前一个再依赖于再前一个”这种链式关系的简化思维。）

3. 子序列 DP 基本功（LIS 变体）：

   P1020 [NOIP1999 普及组] 导弹拦截 （所有子序列 DP 的基石，虽然是 1D DP，但理解其“寻找前驱状态”的过程对理解 2D DP 很有帮助。）

4. 类斐波那契/性质搜索：

   P8682 [蓝桥杯 2019 省 B] 等差数列 （练习如何处理给定集合中的等差关系，侧重于公差的性质分析。）

教练寄语： DP 的本质就是“记录历史”。当 1D 数组存不下历史时，就开 2D；当 2D 太大时，就用哈希表。永远记住：状态定义多一个维度，是为了给未来决策多留一个证据。