This is the last game so make it count, it’s now or never.
不要辜负这最后的比赛,时不我待。 如果序列X_1,X_2,...,X_n满足下列条件,就说它是斐波那契式的: 给定一个严格递增的正整数数组形成序列,找到A中最长的斐波那契式的子序列的长度。如果一个不存在,返回0。 (回想一下,子序列是从原序列A中派生出来的,它从A中删掉任意数量的元素(也可以不删),而不改变其余元素的顺序。例如,[3,5,8]是[3,4,5,6,7,8]的一个子序列) 示例 1: 输入: [1,2,3,4,5,6,7,8] 输出: 5 解释: 最长的斐波那契式子序列为:[1,2,3,5,8] 。
示例 2: 输入: [1,3,7,11,12,14,18] 输出: 3 解释: 最长的斐波那契式子序列有: [1,11,12],[3,11,14] 以及 [7,11,18] 。
提示: 斐波那契数列满足的条件是前两项的和等于第3项的值。暴力求解的方式就是先固定第1项和第2项的值,然后来查找第3项,如果数组中存在第3项的值,说明这3项可以构成一个斐波那契数列,然后在更新第1项和第2项的值,更新结果是 (first, second) -> (second, first+second) 接着重复上面的判断……记录最长的即可。
因为题中说了是一个递增的正整数数组,所以我们可以先把数组中的元素全部存放到集合Set中,查找第3项的时候直接从集合Set中查找即可,来看下代码。 1public int lenLongestFibSubseq(int[] A) { 2 int size = A.length; 3 //先把数组A中的所有元素都存储在Set中 4 Set<Integer> set = new HashSet<>(); 5 for (int num : A) 6 set.add(num); 7 //记录构成的最长斐波那契数列的长度 8 int maxLength = 0; 9 for (int i = 0; i < size; ++i) 10 for (int j = i + 1; j < size; ++j) { 11 //斐波那契数列的第一项 12 int first = A[i]; 13 //斐波那契数列的第二项 14 int second = A[j]; 15 //当前斐波那契数列的长度 16 int len = 2; 17 //斐波那契数列前两项和等于第三项的值,这里 18 //判断数组A中是否存在前两项的和 19 while (set.contains(first + second)) { 20 //如果能构成斐波那契数列,我们需要更新后面的值, 21 //(first, second) -> (second, first+second) 22 second = first + second; 23 first = second - first; 24 //记录当前能构成的斐波那契数列的长度 25 len++; 26 } 27 //更新最大的斐波那契数列长度 28 if (len > maxLength) 29 maxLength = len; 30 } 31 //能构成斐波那契数列,长度必须大于等于3,如果小于3, 32 //说明不能构成斐波那契数列,直接返回0,否则返回maxLength 33 return maxLength >= 3 ? maxLength : 0; 34}
动态规划首先要找出状态的定义和状态转移公式。定义dp[i][j]表示以A[i]和A[j]结尾的斐波那契数列的最大长度。也就是[……,A[i],A[j]]构成的斐波那契数列的最大长度。 状态转移公式就是,如果以A[i]和A[j]结尾能构成斐波那契数列,那么在这个数列A[i]之前必定有一个值A[k]满足A[k]+A[i]=A[j];所以如果确定了A[i]和A[j]的值之后,我们可以往前来找A[k],那么转移公式就是
dp[i][j]=dp[k][i]+1;
所以大致代码我们就很容易写出来了。
1 for (int j = 2; j < length; j++) {//确定A[j] 2 for (int i = j - 1; i > 0; i--) {//确定A[i] 3 for (int k = i - 1; k >= 0; k--) {//往前查找A[k] 4 if (A[k] + A[i] == A[j]) { 5 dp[i][j] = dp[k][i] + 1; 6 //如果找到就终止内层循环,不在往前查找了 7 break; 8 } else if (A[k] + A[i] < A[j]) { 9 //题中说了是递增的正整数数组,如果当前A[k] 10 //小了,那么前面的就更小,没有合适的,没必要 11 //在往前找了,直接终止内层循环 12 break; 13 } 14 } 15 maxLength = Math.max(maxLength, dp[i][j]); 16 } 17 }
我们来看下最终代码 1public int lenLongestFibSubseq(int[] A) { 2 //记录最大的斐波那契数列的长度 3 int maxLength = 0; 4 int length = A.length; 5 int[][] dp = new int[length][length]; 6 for (int j = 2; j < length; j++) {//确定A[j] 7 for (int i = j - 1; i > 0; i--) {//确定A[i] 8 for (int k = i - 1; k >= 0; k--) {//往前查找A[k] 9 if (A[k] + A[i] == A[j]) { 10 dp[i][j] = dp[k][i] + 1; 11 //如果找到就终止内层循环,不在往前查找了 12 break; 13 } else if (A[k] + A[i] < A[j]) { 14 //题中说了是递增的正整数数组,如果当前A[k] 15 //小了,那么前面的就更小,没有合适的,没必要 16 //在往前找了,直接终止内层循环 17 break; 18 } 19 } 20 maxLength = Math.max(maxLength, dp[i][j]); 21 } 22 } 23 //注意数列长度统计的时候没有统计前面两项,如果能构成 24 //斐波那契数列最后还需要加上 25 return maxLength > 0 ? maxLength + 2 : 0; 26}
上面代码确定A[j]和A[i],查找A[k]的时候是一个个往前查,整个计算时间复杂度比较高,我们还可以把遍历过的A[j]和他对应的下标存放到map中,在查找的时候直接从map中查找,这样时间复杂度就会从O(n^3)降到O(n^2),来看下代码。
1public int lenLongestFibSubseq(int[] A) { 2 //记录最大的斐波那契数列的长度 3 int maxLength = 0; 4 int length = A.length; 5 int[][] dp = new int[length][length]; 6 Map<Integer, Integer> map = new HashMap<>(); 7 for (int j = 0; j < length; j++) {//确定A[j] 8 map.put(A[j], j); 9 for (int i = j - 1; i > 0; i--) {//确定A[i] 10 //因为是递增的,如果A[j]和A[i]之间相差比较大, 11 //就不需要再往前查找了 12 if (A[j] - A[i] >= A[i]) 13 continue; 14 //通过map往前查找A[k] 15 int k = map.getOrDefault(A[j] - A[i], -1); 16 //如果k不等于-1,说明在数组中找到了A[k]这个值 17 if (k >= 0) { 18 dp[i][j] = dp[k][i] + 1; 19 maxLength = Math.max(maxLength, dp[i][j]); 20 } 21 } 22 } 23 return maxLength > 0 ? maxLength + 2 : 0; 24}
对于题中的条件是递增的数量,也就是有序的,所以我们还可以使用双指针来解决,当确定A[j]之后,我们在A[j]的前面来使用两个指针来找和等于A[j]的两个值,这里以示例一为例看下视频 最后再来看下代码 1public int lenLongestFibSubseq(int[] A) { 2 //记录最大的斐波那契数列的长度 3 int maxLength = 0; 4 int length = A.length; 5 int[][] dp = new int[length][length]; 6 for (int j = 2; j < length; j++) {//确定A[j] 7 //左右两个指针 8 int left = 0; 9 int right = j - 1; 10 while (left < right) { 11 //两个指针指向值的和 12 int sum = A[left] + A[right]; 13 if (sum > A[j]) { 14 //因为数组是递增的,如果两个指针指向的值 15 //大了,那么右指针往左移一步来减小他俩的和 16 right--; 17 } else if (sum < A[j]) { 18 //如果两个指针指向的值小了,那么左指针往 19 //右移一步来增大他俩的和 20 left++; 21 } else { 22 //如果两个指针指向的和等于A[j],说明这两个指针 23 //指向的值和A[j]可以构成斐波那契数列 24 dp[right][j] = dp[left][right] + 1; 25 maxLength = Math.max(maxLength, dp[right][j]); 26 right--; 27 left++; 28 } 29 } 30 } 31 return maxLength > 0 ? maxLength + 2 : 0; 32}
|