[LeetCode] 873. Length of Longest Fibonacci Subsequence

[grandyang]

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 sequenceA 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:

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

Example 2:

Input: [1,3,7,11,12,14,18]
Output: 3
Explanation:
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++.)

这道题给了我们一个数组，让找其中最长的斐波那契序列，既然是序列而非子数组，那么数字就不必挨着，但是顺序还是需要保持，题目中说了数组是严格递增的，其实博主认为这个条件可有可无的，反正又不能用二分搜索。关于斐波那契数列，想必我们都听说过，简而言之，除了前两个数字之外，每个数字等于前两个数字之和。举个生动的例子，大学食堂里今天的汤是昨天的汤加上前天的汤。哈哈，是不是瞬间记牢了。那么既然要找斐波那契数列，首先要确定起始的两个数字，之后的所有的数字都可以通过将前面两个数组相加得到，那么比较直接暴力的方法，就是遍历所有的两个数字的组合，以其为起始的两个数字，然后再用个 while 循环，不断检测两个数字之和是否存在，那么为了快速查找，要使用一个 HashSet 先把原数组中所有的数字存入，这样就可以进行常数级时间查找了，每找到一个，cnt 自增1（其初始化为2），然后用 cnt 来更新结果 res 即可。最后需要注意的一点是，若 res 小于3的时候，要返回0，因为斐波那契数列的最低消费是3个，参见代码如下：
解法一：

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int res = 0, n = A.size();
        unordered_set<int> st(A.begin(), A.end());
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int a = A[i], b = A[j], cnt = 2;
                while (st.count(a + b)) {
                    b = a + b;
                    a = b - a;
                    ++cnt;
                }
                res = max(res, cnt);
            }
        }
        return (res > 2) ? res : 0;
    }
};

上面的解法存在着一些重复计算，因为当选定的两个起始数字为之前的某个斐波那契数列中的两个数字时，后面的所有情况在之前其实就已经计算过了，没有必要再次计算。所以可以使用动态规划 Dynamic Programming 来优化一下时间复杂度，这道题的 DP 定义式也是难点之一，一般来说，对于子数组子序列的问题，我们都会使用一个二维的 dp 数组，其中 dp[i][j] 表示范围 [i, j] 内的极值，但是在这道题，这种定义方式绝对够你喝两壶，基本无法写出状态转移方程，因为这道题有隐藏信息 Hidden Information，就算你知道了子区间 [i, j] 内的最长斐波那契数列的长度，还是无法更新其他区间，因为没有考虑隐藏信息。再回过头来看一下斐波那契数列的定义，从第三个数开始，每个数都是前两个数之和，所以若想增加数列的长度，这个条件一定要一直保持，比如对于数组 [1, 2, 3, 4, 7]，在子序列 [1, 2, 3] 中以3结尾的斐氏数列长度为3，虽然 [3, 4, 7] 也可以组成斐氏数列，但是以7结尾的斐氏数列长度更新的时候不能用以3结尾的斐氏数列长度的信息，因为 [1, 2, 3, 4, 7] 不是一个正确的斐氏数列，虽然 1+2=3, 3+4=7，但是 2+3!=4。所以每次只能增加一个长度，而且必须要知道前两个数字，正确的 dp[i][j] 应该是表示以 A[i] 和 A[j] 结尾的斐氏数列的长度，很特别吧，之前好像都没这么搞过。

接下来看该怎么更新 dp 数组，我们还是要确定两个数字，跟之前的解法不同的是，先确定一个数字，然后遍历之前比其小的所有数字，这样 A[i] 和 A[j] 两个数字确定了，此时要找一个比 A[i] 和 A[j] 都小的数，即 A[i]-A[j]，若这个数字存在的话，说明斐氏数列存在，因为 [A[i]-A[j], A[j], A[i]] 是满足斐氏数列要求的。这样状态转移就有了，dp[j][i] = dp[indexOf(A[i]-A[j])][j] + 1，可能看的比较晕，但其实就是 A[i] 加到了以 A[j] 和 A[i]-A[j] 结尾的斐氏数列的后面，使得长度增加了1。这个更新方式感觉跟之前那道 Coin Change 有着异曲同工之妙。不过前提是 A[i]-A[j] 必须要在原数组中存在，而且还需要知道某个数字在原数组中的坐标，那么就用 HashMap 来建立数字跟其坐标之间的映射。可以事先把所有数字都存在 HashMap 中，也可以在遍历i的时候建立，因为我们只关心位置i之前的数字。这样在算出 A[i]-A[j] 之后，在 HashMap 查找差值是否存在，不存在的话赋值为 -1。在更新 dp[j][i] 的时候，我们看 A[i]-A[j] < A[j] 且 k>=0 是否成立，因为 A[i]-A[j] 是斐氏数列中最小的数，且其位置k必须要存在才能更新。否则的话更新为2。最后还是要注意，若 res 小于3的时候，要返回0，因为斐波那契数列的最低消费是3个，参见代码如下：

解法二：

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int res = 0, n = A.size();
        unordered_map<int, int> m;
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            m[A[i]] = i;
            for (int j = 0; j < i; ++j) {
                int k = m.count(A[i] - A[j]) ? m[A[i] - A[j]] : -1;
                dp[j][i] = (A[i] - A[j] < A[j] && k >= 0) ? (dp[k][j] + 1) : 2;
                res = max(res, dp[j][i]);
            }
        }
        return (res > 2) ? res : 0;
    }
};

Github 同步地址:

#873

类似题目：

Split Array into Fibonacci Sequence

Fibonacci Number

Coin Change

参考资料：

https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/

https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/discuss/152343/C%2B%2BJavaPython-Check-Pair

LeetCode All in One 题目讲解汇总(持续更新中...)