线性动态规划：最长斐波那契子序列的长度 题目描述： 给定一个严格递增的正整数数组 arr，找到 arr 中最长的斐波那契式子序列的长度。如果一个序列满足以下条件，则称之为斐波那契式子序列： 序列长度至少为 3 对于所有满足 i ≥ 2 的位置，都有 X_ i = X_ {i-1} + X_ {i-2} 例如： 输入：arr = [ 1,2,3,4,5,6,7,8 ] 输出：5 解释：最长的斐波那契子序列是 [ 1,2,3,5,8 ] 解题过程： 步骤1：理解问题本质 我们需要在严格递增的数组中找到一个子序列（不要求连续），满足斐波那契数列的性质 序列中的每个数（从第三个开始）都等于前两个数之和 由于数组严格递增，我们可以利用这个特性来优化搜索 步骤2：定义状态 设 dp[ i][ j] 表示以 arr[ i] 和 arr[ j ] 作为最后两个元素的斐波那契子序列的最大长度 其中 i < j，arr[ i] 是倒数第二个元素，arr[ j ] 是最后一个元素 步骤3：状态转移方程 对于每个位置对 (i, j)，我们寻找前一个元素 arr[ k]，使得 arr[ k] + arr[ i] = arr[ j ] 如果存在这样的 k（k < i），那么 dp[ i][ j] = dp[ k][ i ] + 1 如果不存在这样的 k，那么 dp[ i][ j] = 2（只有 arr[ i] 和 arr[ j ] 两个元素） 步骤4：寻找前驱元素 由于数组严格递增，我们可以用哈希表记录每个元素的值和索引的映射 对于给定的 arr[ i] 和 arr[ j]，前一个元素应该是 arr[ k] = arr[ j] - arr[ i ] 如果 arr[ k] 存在且 k < i，那么我们就找到了一个合法的前驱 步骤5：算法实现细节 创建哈希表记录元素到索引的映射 初始化一个二维dp数组，所有值初始化为2 遍历所有可能的 (i, j) 对，其中 i < j 对于每个 (i, j)，计算前一个元素值 prev = arr[ j] - arr[ i ] 如果 prev 存在且其索引 k < i，则更新 dp[ i][ j] = dp[ k][ i ] + 1 在过程中记录遇到的最大长度 步骤6：边界情况处理 如果数组长度小于3，直接返回0 如果找不到长度≥3的斐波那契子序列，返回0 注意dp数组的初始值都是2，因为任意两个数都可以看作是长度为2的序列 步骤7：复杂度分析 时间复杂度：O(n²)，需要遍历所有 (i, j) 对 空间复杂度：O(n²)，用于存储dp数组 这个解法巧妙地利用了动态规划来记录以每对元素结尾的斐波那契子序列长度，通过哈希表快速查找前驱元素，从而在严格递增数组的特性下高效解决问题。