如果数组 arr 中存在三个下标 i、j、k 满足 arr[i]>arr[j]>arr[k] 且 arr[k]+arr[j]=arr[i]，则 arr[k]、arr[j] 和 arr[i] 三个元素组成一个斐波那契式子序列。由于数组 arr 严格递增，因此 arr[i]>arr[j]>arr[k] 等价于 i>j>k。

把这道题的官解再次细化一下，可视化一下，这样理解起来更容易一些。

代码如下：

区间dp；官解，值得学习；这道题说明了打表的过程是依赖状态转移方程的

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        int cnt = 0;
        for(int val : arr){
            map.put(val,cnt);
            cnt++;
        }
        int ans = -1;
        int[][] dp = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = i - 1; j >= 0 && arr[i] < 2 * arr[j]; j--){
                int k = map.getOrDefault(arr[i]-arr[j],-1);
                if(k >= 0){//k=0时，意思是取下标为0的元素为斐列的上一个元素
                    dp[j][i] = Math.max(dp[k][j]+1,3);
                }
                ans = Math.max(dp[j][i],ans);
            }
        }
        return ans;
    }
}