最长的斐波那契子序列的长度【动态规划解决】

最长的斐波那契子序列暴力破解请移步-> 暴力破解法

//动态规划
class Solution {
   
    public int lenLongestFibSubseq(int[] arr) {
   
        //使用map集合来存储数组元素以便于更快的找到值所对应的下标
        Map<Integer, Integer> indices = new HashMap<Integer, Integer>();
        int n = arr.length;
        for (int i = 0; i < n; i++) {
   
             //这里将数组arr元素的值当作键
            indices.put(arr[i], i);
        }
        //二维数组dp用来存放以数j和数i结尾的数列长度
        int[][] dp = new int[n][n]; 
        int ans = 0;
        //arr[k] +  arr[j] = arr[i]
        //来寻找arr[i]这个数
        for (int i = 2; i < n; i++) {
    
            //从i这个位置依次往前找，arr[j] * 2 > arr[i]：因为arr[j] 之前的数arr[k]一定比arr[j]小,
            //所以两个arr[j]不能等于arr[i]时，arr[k] + arr[j] 一定不会等于arr[i]
            for (int j = i - 1; j >= 0 && arr[j] * 2 > arr[i]; j--) {
    
                //从集合indices中获取arr[k]值是否存在如果存在则输出它的下标，不存在则输出-1
                int k = indices.getOrDefault(arr[i] - arr[j], -1); 
                if (k >= 0) {
   
                    存在时则直接就赋值，因为数组dp初始值为0，所以要判断
                    dp[j][i] = Math.max(dp[k][j] + 1, 3); 
                }
                ans = Math.max(ans, dp[j][i]);
            }
        }
        return ans;
    }
}