题目

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

n >= 3

对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。

例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

示例 1：输入: arr = [1,2,3,4,5,6,7,8] 输出: 5

解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

示例 2：输入: arr = [1,3,7,11,12,14,18] 输出: 3

解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。

提示：3 <= arr.length <= 1000

1 <= arr[i] < arr[i + 1] <= 10^9

注意：本题与主站 873 题相同：

解题思路分析

1、暴力法；时间复杂度O(n^3)，空间复杂度O(n)

func lenLongestFibSubseq(arr []int) int {
   n := len(arr)
   m := make(map[int]bool)
   for i := 0; i < n; i++ {
      m[arr[i]] = true
   }
   res := 0
   for i := 0; i < n; i++ {
      for j := i + 1; j < n; j++ {
         count := 2
         a, b := arr[i], arr[j]
         for m[a+b] == true {
            count++
            a, b = b, a+b
         }
         if count > res && count > 2 {
            res = count
         }
      }
   }
   return res
}

2、动态规划；时间复杂度O(n^2)，空间复杂度O(n^2)

func lenLongestFibSubseq(arr []int) int {
   n := len(arr)
   m := make(map[int]int)
   for i := 0; i < n; i++ {
      m[arr[i]] = i
   }
   dp := make([][]int, n)
   for i := 0; i < n; i++ {
      dp[i] = make([]int, n)
   }
   res := 0
   for i := 0; i < n; i++ {
      for j := i + 1; j < n; j++ {
         dp[i][j] = 2
      }
   }
   for i := 0; i < n; i++ {
      for j := 0; j < i; j++ {
         index, ok := m[arr[i]-arr[j]]
         if ok && arr[index] < arr[j] {
            dp[j][i] = dp[index][j] + 1
            if dp[j][i] > 2 && dp[j][i] > res {
               res = dp[j][i]
            }
         }
      }
   }
   return res
}

总结

Medium题目，题目同leetcode 873.最长的斐波那契子序列的长度