《LeetCode 1218 最长定差子序列 || LeetCode 873 最长的斐波那契序列的长度》
一、题目
二、做题思路
2.1 状态表示（核心基础）
本题要求计算最长等差子序列的长度，其中相邻元素差固定为difference。
使用哈希表hash[val]表示以数值val结尾的最长定差子序列的长度，便于通过前驱值快速查询和更新。
2.2 状态转移方程（关键难点）
遍历数组时，对于当前元素arr[i]，其作为子序列结尾的最长长度等于前驱arr[i] - difference的结尾长度加 1。若前驱不存在，则长度为 1。
因此转移为：hash[arr[i]] = hash[arr[i] - difference] + 1（其中不存在的键默认值为 0）。
2.3 初始化（边界防护）
先初始化第一个元素：hash[arr[0]] = 1，作为起始子序列。
2.4 填表顺序（递推方向）
从左到右遍历数组（i从 1 到n-1），因为每个状态只依赖之前出现的同差值前驱，顺序遍历可保证前驱已被处理。
2.5 返回值（目标映射）
维护全局最大值ret，每次更新hash[arr[i]]后取max，最终返回ret，即为整个数组的最长定差子序列长度。
三、代码
class Solution { public: int wiggleMaxLength(vector<int>& nums) { int n = nums.size(); // 边界处理：空数组无摆动序列 if (n == 0) return 0; // 1. 创建dp表 // f[i] : 以 nums[i] 结尾，且最后一段比较关系为“上升”（nums[i-1] < nums[i]）的摆动序列的最大长度 // g[i] : 以 nums[i] 结尾，且最后一段比较关系为“下降”（nums[i-1] > nums[i]）的摆动序列的最大长度 // 初始化：每个元素自身可构成长度为 1 的摆动序列（既可以是上升也可以是下降的起点） vector<int> f(n, 1); vector<int> g(n, 1); // 2. 填表顺序：从左到右（i 从 1 到 n-1），因为 f[i]/g[i] 依赖所有 j < i 的状态 for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { // 3. 状态转移方程： // 若 nums[i] > nums[j]，则可以将 nums[i] 接在“下降”结尾的序列后面（g[j]），形成上升结尾的序列， // 长度 = g[j] + 1；同时保留 f[i] 原有的值（可能通过其他 j 得到更长的长度） if (nums[i] > nums[j]) { f[i] = max(f[i], g[j] + 1); } // 若 nums[i] < nums[j]，则可以将 nums[i] 接在“上升”结尾的序列后面（f[j]），形成下降结尾的序列， // 长度 = f[j] + 1；同时保留 g[i] 原有的值 else if (nums[i] < nums[j]) { g[i] = max(g[i], f[j] + 1); } // 若相等，无法构成摆动，跳过（状态保持不变） } } // 4. 返回值：所有 f[i] 和 g[i] 中的最大值 int ret = 1; for (int i = 0; i < n; i++) { ret = max(ret, max(f[i], g[i])); } return ret; } };四、流程图
五、题目
六、做题思路
6.1 状态表示（核心基础）
本题要求计算最长的斐波那契式子序列的长度。由于斐波那契式序列由前两个元素决定后续，定义dp[j][i]表示以arr[j]和arr[i]作为最后两个元素的斐波那契式子序列的最长长度（j < i）。
6.2 状态转移方程（关键难点）
枚举最后两个元素的下标(j, i)，设前一个值为a = arr[i] - arr[j]。若a < arr[j]（保证更小且符合递增顺序）且a在哈希表中存在（索引为k），则可以将arr[i]追加到以(arr[k], arr[j])结尾的序列后面，长度更新为dp[j][i] = dp[k][j] + 1。否则dp[j][i]保持为 2。
6.3 初始化（边界防护）
所有dp[j][i]初始化为 2，因为任意两个不同元素至少可以构成长度为 2 的前缀。
6.4 填表顺序（递推方向）
按i从 2 到n-1，内层j从 1 到i-1遍历。因为dp[j][i]依赖dp[k][j]（其中k < j），而dp[k][j]已在处理更小的i（即i = j时）计算过，所以从左到右按列（或按i递增）的顺序可保证前置状态已就绪。
6.5 返回值（目标映射）
维护全局最大值ret，每次更新后取max。最终若ret == 2（表示不存在长度 ≥ 3 的序列），返回0；否则返回ret。
七、代码
class Solution { public: int lenLongestFibSubseq(vector<int>& arr) { // 1. 构建哈希表：存储每个值对应的索引（值唯一，因为 arr 严格递增） unordered_map<int, int> hash; int n = arr.size(); for (int i = 0; i < n; i++) { hash[arr[i]] = i; } // 2. 创建dp表（二维） // dp[j][i] 表示以 arr[j] 和 arr[i] 作为最后两个元素的斐波那契式子序列的最长长度 // 其中 j < i，初始化为 2（任何两个元素至少可以构成长度为 2 的“基础”序列） vector<vector<int>> dp(n, vector<int>(n, 2)); int ret = 2; // 全局最长长度，初始为 2 // 3. 填表顺序：按 i 从 2 到 n-1，内层 j 从 1 到 i-1 // 因为 dp[j][i] 依赖于 dp[k][j]（k < j），而 dp[k][j] 已经在前面的 i'（即 j）时计算过 for (int i = 2; i < n; i++) { for (int j = 1; j < i; j++) { // 4. 状态转移方程： // 若存在一个数 a = arr[i] - arr[j]，且 a < arr[j]（保证 a 是更小的数，且 arr 严格递增）， // 并且 a 在哈希表中存在，假设其索引为 k = hash[a]， // 则可以形成长度为 dp[k][j] + 1 的斐波那契式子序列（将 arr[i] 追加到以 arr[k], arr[j] 结尾的序列后面） int a = arr[i] - arr[j]; if (a < arr[j] && hash.count(a)) { int k = hash[a]; dp[j][i] = dp[k][j] + 1; ret = max(ret, dp[j][i]); } } } // 5. 返回值：若 ret 仍为 2，则不存在长度 ≥ 3 的斐波那契式子序列，返回 0；否则返回 ret return (ret == 2) ? 0 : ret; } };