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

题目描述

本题目来自LeetCode上的『873. 最长的斐波那契子序列的长度』

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

n >= 3
对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

示例1：

输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

提示

3 <= arr.length <= 1000
1 <= arr[i] < arr[i + 1] <= 10^9

题解

设 $dp[j][k]$ 表示以 $arr[j]$ 和 $arr[k]$ 为最后两个数的斐波那契子序列的最大长度。
若已知后两个数 $arr[j]$ 和 $arr[k]$，可以直接算得前一个满足条件的数 $arr[i]=arr[k]-arr[j]$，如果能够找到 $arr[i]$，有 $dp[j][k]=dp[i][j]+1$，因为若 $arr[i]\ \ arr[j]\ \ arr[k]$ 能够组成斐波那契数列，那么它的长度最小为 $3$。有以下转移方程
$$
dp[j][k]=max(dp[i][j]+1,3)
$$
为了方便查找，将每个元素对应的下标保存在哈希表中。
$dp[j][k]$ 初始化全部为 $0$。
可行性剪枝： 因为 $arr[i]<arr[j]<arr[k]$，因此当 $arr[k]-arr[j]\ge arr[j]$ 时就不存在满足要求的 $arr[i]$，但是这个值在哈希表中还是有可能被找到，需要剪枝。
注：另一种方法就是 $dp[j][k]$ 初始化全部为 $2$，因为 $arr[i]$ 唯一，转移方程就变为 $dp[j][k]=dp[i][j]+1$，在返回答案时需要进行判断，$ans<3$ 需要返回 $0$。

代码

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        int dp[1010][1010] = {0};
        int ans = 0;
        unordered_map<int, int> mp;
        for (int i = 0; i < n; ++i) mp[arr[i]] = i;

        for (int k = 0; k < n; ++k) {
            for (int j = k - 1; j >= 0; --j) {
                if (arr[k] - arr[j] >= arr[j]) break;
                auto it = mp.find(arr[k] - arr[j]);
                if (it != mp.end()) {
                    dp[j][k] = max(dp[it->second][j] + 1, 3);
                }
                ans = max(ans, dp[j][k]);
            }
        }

        return ans;
    }
};

或者

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        int dp[1010][1010] = {0};
        int ans = 0;
        unordered_map<int, int> mp;
        for (int i = 0; i < n; ++i) mp[arr[i]] = i;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                dp[i][j] = 2;
            }
        }

        for (int k = 0; k < n; ++k) {
            for (int j = k - 1; j >= 0; --j) {
                if (arr[k] - arr[j] >= arr[j]) break;
                auto it = mp.find(arr[k] - arr[j]);
                if (it != mp.end()) {
                    dp[j][k] = dp[it->second][j] + 1;
                }
                ans = max(ans, dp[j][k]);
            }
        }

        return ans > 2 ? ans : 0;
    }
};