LeetCode每日一题——873. 最长的斐波那契子序列的长度

简介: 如果序列 X_1, X_2, …, X_n 满足下列条件,就说它是 斐波那契式 的:

题目

如果序列 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

思路

典型的动态规划,只不过状态和状态转移方程有点难找

定义状态

dp[i][j]表示以A[i],A[j]结尾的最长斐波那契子序列长度。

转移方程

这里我们考虑在A[i]之前有某个数字A[k],那么是不是应该满足如下式子

A[k] + A[i] == A[j]

那么我们就可以写出来状态转移方程

dp[i][j] = max(dp[k][i]+1)

由于给定数组严格递增,这里使用一个map,将A[i]与i映射起来。即 map[A[i]] = i,即可实现找到max(dp[k][i]+1)

题解

def lenLongestFibSubseq(arr: List[int]) -> int:
    n = len(arr)
    if n <= 2:
        return 0
    max_ = 0
    #  初始化dp和map
    dp, temp = [[1] * n for i in range(n)], {}
    for i in range(n):
        for j in range(i+1,n):
            dp[i][j] = 2
    for i in range(n):
        temp[arr[i]] = i
    for i in range(n):
        for j in range(i+1, n):
            res = arr[j] - arr[i]
            # 找到k的值
            if res in temp.keys():
                dp[i][j] = max(dp[i][j], dp[temp.get(res)][i]+1)
                # 更新最大值
                max_ = max(max_, dp[i][j])
    return max_ if max_ > 2 else 0
目录
相关文章
|
6天前
|
存储
力扣-2904最短且字典序最小的美丽子序列
力扣-2904最短且字典序最小的美丽子序列
6 1
|
7天前
|
存储 自然语言处理 算法
LeetCode题目115:不同子序列
LeetCode题目115:不同子序列
|
12天前
|
算法 Java Go
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
14 0
|
1月前
|
算法
代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
37 1
|
1月前
|
测试技术
【力扣】392.判断子序列
【力扣】392.判断子序列
|
3天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
3天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
4天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
4天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
4天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值