873. 最长的斐波那契子序列的长度

Difficulty
Medium
Tags
n数之和
动态规划
URL
https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence/
Star
如果序列 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：
输出:3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。
提示：
  • 3 <= arr.length <= 1000
  • 1 <= arr[i] < arr[i + 1] <= 10^9

法1 动态规划 + hash

思路
dp[i][j]表示以arr[j]，arr[i]结尾的最长斐波那契子序列长度。所以就需要找arr[k],使得arr[k] + arr[j] ==arr[i]。 有点三数字之和的意思了。
这里采用hash来记录每个数字的下标。这样更快的找到第三个数字。
找到第三个数字之后，那么dp[i][j] = dp[j][k] + 1
默认的dp[i][j] 应该等于2，这样如果有下一个数字就可以直接+1得到结果了。
题解
class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        hash_map= {}
        for i in range(len(arr)):
            hash_map[arr[i]] = i

        # 默认值设置为2，这样当找到第三个数字，可以直接+1得到结果
        dp = [[2]*len(arr) for _ in arr]

        res = 2
        for i in range(1, len(arr)):
            for j in range(0, i):
                if arr[i]-arr[j] in hash_map and hash_map[arr[i]-arr[j]] < j:
                    # 得到第三个数字的下标
                    k = hash_map[arr[i]-arr[j]]
                    dp[i][j] = dp[j][k] + 1
                    res = max(res, dp[i][j])

        return res if res > 2 else 0

法 2 动态规划 + 双指针

思路
定义好 状态dp[i][j] 为 以 arr[i][j] 结尾的 数列，那么就需要找一个 arr[k]， 使得arr[k] + arr[j] = arr[i]， 有点类似三数之和，因为是递增的，所以采用双指针来找 j 和 k。
class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        # dp[i][j] 表示以 arr[j] arr[i] 结尾的 序列
        dp = [[0] * len(arr) for _ in arr]
        
        res = 0
        for i in range(2, len(arr)):
            k, j = 0, i-1
            while k < j:
                temp = arr[k] + arr[j]
                if temp == arr[i]:
                    dp[i][j] = max(dp[i][j], dp[j][k] + 1)
                    res = max(res, dp[i][j])
                    k += 1
                    j -= 1
                elif temp > arr[i]:
                    j -= 1
                else:
                    k += 1            
            
        return res + 2 if res > 0 else 0