[LeetCode]Length of Longest Fibonacci Subsequence

栏目: 编程工具 · 发布时间: 6年前

内容简介:A sequenceGiven a

题目描述:

LeetCode 873. Length of Longest Fibonacci Subsequence

A sequence X_1, X_2, ..., X_n is fibonacci-like if:

  • n >= 3
  • X_i + X_{i+1} = X_{i+2}  for all  i + 2 <= n

Given a strictly increasing array  A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A .  If one does not exist, return 0.

( Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A , without changing the order of the remaining elements.  For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8] . )

Example 1:

<strong>Input: </strong>[1,2,3,4,5,6,7,8]
<strong>Output: </strong>5
<strong>Explanation:
</strong>The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

<strong>Input: </strong>[1,3,7,11,12,14,18]
<strong>Output: </strong>3
<strong>Explanation</strong>:
The longest subsequence that is fibonacci-like:
[1,11,12], [3,11,14] or [7,11,18].

Note:

  • 3 <= A.length <= 1000
  • 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
  • (The time limit has been reduced by 50% for submissions in Java, C, and C++.)

题目大意:

求递增正整数组的最长类斐波那契数列。

解题思路:

动态规划(Dynamic Programming)

时间复杂度 O(N^2)

状态转移方程:

dp[y][x + y] = max(dp[y][x + y], dp[x][y] + 1)

上式中, dp[x][y]表示以(x, y)为结尾的类斐波那契数列的长度

Python代码:

class Solution(object):
    def lenLongestFibSubseq(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        vset = set(A)
        dp = collections.defaultdict(lambda: collections.defaultdict(int))
        size = len(A)
        ans = 0
        for i in range(size):
            x = A[i]
            for j in range(i + 1, size):
                y = A[j]
                if x + y not in vset: continue
                dp[y][x + y] = max(dp[y][x + y], dp[x][y] + 1)
                ans = max(dp[y][x + y], ans)
        return ans and ans + 2 or 0

以上所述就是小编给大家介绍的《[LeetCode]Length of Longest Fibonacci Subsequence》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Python for Everyone

Python for Everyone

Cay S. Horstmann、Rance D. Necaise / John Wiley & Sons / 2013-4-26 / GBP 181.99

Cay Horstmann's" Python for Everyone "provides readers with step-by-step guidance, a feature that is immensely helpful for building confidence and providing an outline for the task at hand. "Problem S......一起来看看 《Python for Everyone》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

SHA 加密
SHA 加密

SHA 加密工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具