动态规划子序列标题系列一＞最长斐波那契子序列的长度

标题： 

---

剖析： 

---

代码： 

2. public int lenLongestFibSubseq(int[] arr) {
3.         int n = arr.length;
4.         int ret = 2;
5.         Map<Integer,Integer> hash = new HashMap<>();
6.         int[][] dp = new int[n][n];
8.         //把元素和下标绑定起来，便于找下标K
9.         for(int i = 0; i < n; i++)
10.             hash.put(arr[i],i);
12.         for(int i = 0; i < n; i++)
13.             for(int j = 0; j < n; j++)
14.                 dp[i][j] = 2;
16.         for(int j = 2; j < n; j++){//固定第二个数
17.             for(int i = 1; i < j; i++){//固定倒数第二个数
18.                 int a = arr[j]-arr[i];
19.                 int b = arr[i];
20.                 if(a < b && hash.containsKey(a)) dp[i][j] = dp[hash.get(a)][i]+1;
22.                 ret = Math.max(ret, dp[i][j]);
23.             }
24.         }   
26.         return ret < 3 ? 0 : ret;
27.     }

复制代码