LeetCode 873. Length of Longest Fibonacci Subsequence

[Woodyiiiiiii]

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:

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++.)

---

这道题求的是最长的斐波那契子序列。
首先想到暴力递归的方法，遍历数组内所有不同位置的两个元素，找到符合以这两个元素为起点的斐波那契数列，找到最大子数列值。为了找到满足两数之和的第三个数，递归下去的第四个，第五个···可以用HashSet寻找，达到寻找元素时间复杂度为O(1)。

class Solution {
    public int lenLongestFibSubseq(int[] A) {
        int len = A.length;
        if (len < 3) return 0;
        int res = 0;
        HashSet<Integer> help = new HashSet();
        for (int i = 0; i < len; ++i) {
            help.add(A[i]);
        }
        for (int i = 0; i < len - 1; ++i) {
            for (int j = i + 1; j < len; ++j) {
                int a = A[i], b = A[j], cnt = 2;
                while (help.contains(a + b)) {
                    ++cnt; 
                    b = a + b;
                    a = b - a;
                }
                res = Math.max(res, cnt);
            }
        }
        return res < 3 ? 0 : res;
   

接下来将递归优化为动态规划的方法。因为在递归中，某些情况多算了几遍，动态规划可以解决这个问题。
一般来说，对于子数组子序列的问题，我们都会使用一个二维的 dp 数组，其中 dp[i][j] 表示范围 [i, j] 内的极值，但是在这道题，因为斐波那契数列需要知道前两个数的值，所以dp数组的dp[i][j]表示的是以元素dp[i]结尾的最大斐波那契序列长度。
不同于以前多数动态规划方法那样从前往后确定dp数值，但是dp的值是多种情况(子斐波那契数列)的长度汇总的，无法确定。所以我们向后寻找，状态转移是dp[indexOf(A[i]-A[j])][j] + 1，即若存在等于两数之差的元素，则长度加一(同Coin Change 2)。同时利用HashMap建立数组元素和数组下标位置的映射，最后也要判断序列长度是否大于2。

class Solution {
    public int lenLongestFibSubseq(int[] A) {
        int res = 0, n = A.length;
        HashMap<Integer, Integer> m = new HashMap();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; ++i) {
            // m[A[i]] = i;
            m.put(A[i], i);
            for (int j = 0; j < i; ++j) {
                int k = m.containsKey(A[i] - A[j]) ? m.get(A[i] - A[j]) : -1;
                dp[j][i] = (A[i] - A[j] < A[j] && k >= 0) ? (dp[k][j] + 1) : 2;
                res = Math.max(res, dp[j][i]);
            }
        }
        return (res > 2) ? res : 0;
    }
}

---

参考资料:

• https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/submissions/
• [LeetCode] 873. Length of Longest Fibonacci Subsequence grandyang/leetcode#873