【教3妹学算法-逐日3题(1)】最长的斐波那契子序列的长度

程序员 · 2024-10-9 10:07:21

插：前些天发现了一个巨牛的人工智能学习网站，普通易懂，风趣幽默，不由得分享一下给各人。点击跳转到网站。
对峙不懈，越努力越荣幸，各人一起学习鸭~~~

2哥：3妹，本日又是高考日。
3妹：瞎说什么，高考是6月7号
2哥：上海的同砚高考啊。
3妹：对哦，前段时间上海疫情，以是调教推迟了一个月
2哥：是的
3妹：那我也到场自己的“高考”，做个算法题吧
标题：

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是斐波那契式的：
n >= 3
对于全部 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
（追念一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉恣意数目的元素（也可以不删），而不改变别的元素的次序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
示例 1：
输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
表明: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
示例 2：
输入: arr = [1,3,7,11,12,14,18]
输出: 3
表明: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。
提示：
3 <= arr.length <= 1000
1 <= arr < arr[i + 1] <= 10^9
思绪：

动态规划
如果数组 arr 中存在三个下标 i、j、k 满足arr>arr[j]>arr[k] 且 arr[k]+arr[j]=arr，则arr[k]、arr[j] 和 arr 三个元素构成一个斐波那契子序列。由于数组arr 严格递增，因此 arr>arr[j]>arr[k] 等价于i>j>k。
当下标 i 确定时，任何小于下标 i的下标 j 都大概满足 arr[j] 是某个斐波那契子序列中arr 前面的一个数字，因此只有当确定斐波那契子序列的最后两个数字时，才能确定整个斐波那契子序列。
定义二维数组 dp 表现以每个下标对的元素作为最后两个数字的斐波那契子序列的最大长度。当i>j 时，dp[j] 表现以 arr[j] 和arr 作为最后两个数字的斐波那契子序列的最大长度。初始时dp 中的全部值都是 0。
为了盘算dp[j] 的值，必要得到该斐波那契序列中位于arr[j] 前面的数字，该数字是arr−arr[j]。如果 arr−arr[j] 存在于数组arr 中，且该数字小于arr[j]，则用 k 表现其下标，有arr[k]+arr[j]=arr。因此在以 arr[k] 和arr[j] 作为最后两个数字的斐波那契子序列的反面添加arr，即可得到以arr[j] 和arr 作为最后两个数字的斐波那契子序列。
根据斐波那契子序列的定义可知，斐波那契子序列的长度至少为 3。当dp[k][j]≥3 时，\textit{dp}[j] = dp[j]=dp[k][j]+1。当 dp[k][j]<3 时，以arr[k] 和arr[j] 作为最后两个数字的斐波那契子序列并不存在，但是以arr[j] 和arr 作为最后两个数字的斐波那契子序列存在，此时有dp[j]=3。
假设当arr−arr[j] 不存在于数组中时，k<0，则完备的状态转移方程如下：
dp[j]= max(dp[k][j]+1,3); 0<=k<j;
dp[j]= 0; k<0 || k>=j;
java代码：

class Solution { public int lenLongestFibSubseq(int[] arr) { Map<Integer, Integer> indices = new HashMap<Integer, Integer>(); int n = arr.length; for (int i = 0; i < n; i++) { indices.put(arr, i); } int[][] dp = new int[n][n]; int ans = 0; for (int i = 0; i < n; i++) { for (int j = i - 1; j >= 0 && arr[j] * 2 > arr; j--) { int k = indices.getOrDefault(arr - arr[j], -1); if (k >= 0) { dp[j] = Math.max(dp[k][j] + 1, 3); } ans = Math.max(ans, dp[j]); } } return ans; }}

【教3妹学算法-逐日3题(1)】最长的斐波那契子序列的长度

所属分类: 问答交流

新帖推荐: 30日

推荐作品