讨论/《动态规划精讲(一)》 - 最长的斐波那契子序列的长度/
《动态规划精讲(一)》 - 最长的斐波那契子序列的长度

java版本的动归代码,增加了注释如下:

class Solution {
    public int lenLongestFibSubseq(int[] A) {
        int N = A.length;
        Map<Integer, Integer> index = new HashMap();
        for (int i = 0; i < N; ++i)
            index.put(A[i], i);

        Map<Integer, Integer> longest = new HashMap();
        int ans = 0;

        for (int k = 0; k < N; ++k)
            for (int j = 0; j < k; ++j) {
                int i = index.getOrDefault(A[k] - A[j], -1);
                if (i >= 0 && i < j) {
                    // 技巧:使用(i * N + j)将二维数组索引存储到一维数组中去
                    // Encoding tuple (i, j) as integer (i * N + j)
                    int cand = longest.getOrDefault(i * N + j, 2) + 1;
                    longest.put(j * N + k, cand);
                    ans = Math.max(ans, cand);
                }
            }

        return ans >= 3 ? ans : 0;
    }
}

// 作者:力扣 (LeetCode)
// 链接:https://leetcode-cn.com/leetbook/read/dynamic-programming-1-plus/5ruvye/?discussion=haKvSc
// 来源:力扣(LeetCode)
// 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
展开全部 5 讨论