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

发表于： 分类于：
字数： 1266 阅读：≈ 3分钟

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

如果序列 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] 的一个子序列）

思路

基本思想

​ 看到这种求子序列的题目，第一想法是按照滑动窗口进行处理，但是题目描述序列中可以删除一些元素，也就是不是连续序列，所以此时滑动窗口这种求连续序列的方法就无法使用，进而使用动态规划来做；

​ 动态规划最重要的就是确定dp数组的含义，本题中为了找到一个最长的斐波那契数列，需要不断进行累加，也就是不断在原有斐波那契数列末尾arr[k]的基础上增加两个元素arr[i]和arr[j]，使得这三者符合斐波那契数列的特点，所以dp[i][j]的含义就是以arr[i]和arr[j]结尾的最长斐波那契数列的长度；

​ 当前元素为arr[i]，此时arr[j]是从i开始向后任意找一个元素，然后arr[k]代表从0~i-1中任意找一个元素，符合arr[k]+arr[i]=arr[j]即可，相当于一个三层循环，每次针对不同的arr[i]和arr[j]组合都要重新寻找arr[k]，观察到题目中描述元素严格递增，说明没有重复元素，所以我们可以保存元素及其下标的对应关系

​ 一旦有了arr[i]和arr[j]的组合，使用arr[j]-arr[j]就可以得到我们要找的arr[k]，再判断这个元素的下标是不是在0~i-1中即可

执行流程

  1. 初始化dp数组，所有的元素值都为2，因为一旦找到一个最小的斐波那契数列，这个长度为3
  2. 针对不同位置的arr[i]，arr[j]元素的下标从i+1开始
  3. 使用arr[j]-arr[j]得到要找的arr[k]，判断其下标是否符合要求
  4. 不停地向后更新dp
  5. 返回结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    // 序列长度大于3，并且每一个元素都是前两个元素的和
    // 由于可以剔除掉一些元素，所以不能用滑动窗口，需要使用DP
    // dp[i][j]代表以arr[i]和arr[j]结尾，然后从0-i-1之间找一个数
    // 三个数能否组成更长的序列
    //
    public int lenLongestFibSubseq(int[] arr) {
        int res = 0;
        int[][] dp = new int[arr.length][arr.length];

        // 保存元素和其下标之间的对应关系
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; ++i) {
            map.put(arr[i], i);
        }

        // 所有元素初始化为2
        for (int i = 0; i < arr.length; ++i) {
            Arrays.fill(dp[i], 2);
        }
        for (int i = 1; i < arr.length; ++i) {
            int j = i + 1;
            for (; j < arr.length; ++j) {
                // 不用每次都从头遍历一遍找到合法的k
                // 由于元素不重复，所以想要找的arr[k]其实是唯一的
                if (map.containsKey(arr[j] - arr[i])) {
                    int index = map.get(arr[j] - arr[i]);
                    if (index < i) {
                        dp[i][j] = Math.max(dp[i][j], dp[index][i] + 1);
                    }
                }
                // 更新看当前有没有出现最大值
                res = Math.max(res, dp[i][j]);
            }
        }
        return res == 2 ? 0 : res;
    }
}

总结

核心点就在于设计出dp数组的含义，然后动态更新dp数组即可，为了加快代码的运行，需要记录元素及其下标之间的对应关系，这样获取arr[k]时就不用每次都重复遍历了