【算法】【动规】最长斐波那契子序列的长度
2023-12-21 17:41:22
跳转汇总链接
2.6 最长的斐波那契子序列的长度
如果序列 X_1, X_2, …, X_n 满足下列条件,就说它是 斐波那契式 的:
n >= 3
对于所有 i + 2 <= n,都有 X_i + X_{i+1} = X_{i+2}给定一个严格递增的正整数数组形成序列 arr ,找到 arr 中最长的斐波那契式的子序列的长度。
如果一个不存在,返回 0 。
- 状态表示
- 考虑到两个连续数字才能推导出这一组斐波那契数,又需要我们以 “一个位置为自序列的结尾” 这样的方法去定义状态表示,于是考虑用如下定义:
- dp[i][j] 表示,以 i 位置(前)以及 j 位置(后)的元素为结尾的所有子序列中,最长的斐波那契子序列的长度
- 状态转移方程
-
首先我们需要填写的是 dp[i][j]
-
其次已知的值是 arr[i] 和 arr[j] 作为斐波那契子序列的结尾
-
设倒数第三个数位置为 k 元素为 a,arr[i] 为 b,arr[j] 为 c,可以分为 a = c - b 是否存在,这两种大情况
a 存在,且 a < b,dp[i][j] = dp[k][i] + 1; a 存在,但 b < a < c,dp[i][j] = 2; a 不存在,dp[i][j] = 2;
-
式子应该很好理解,但是 k 的位置,也就是 a 的下标,却是不好确定的
-
考虑在不在问题,同时题目表明 arr 是严格递增的,我们可以对状态转移方程做一个提前优化
-
- 优化
- 将 <arr 数组的元素,元素下标> ,作为 <key, value> 绑定,存在哈希表中。
- 初始化
- dp[][] 里都初始化为 2。
- 填表顺序
- 下标从小到大依次填写。
- 返回值
- dp表里的最大值,如果是 2 的话返回 0。
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
int n = arr.size();
int retMax = 0;
// 优化
unordered_map<int, int> pos;
for(int i = 0; i < n; i++) pos[arr[i]] = i;
vector<vector<int>> dp(n, vector(n, 2));
for (int j = 2; j < n; j++) // 最后一个数
{
for(int i = 1; i < j; i++) // 倒数第二个数
{
int a = arr[j] - arr[i];
if(pos.count(a) && pos[a] < pos[arr[i]]) // 如果a存在,且位置正确
{
dp[i][j] = dp[pos[a]][i] + 1;
}
retMax = max(retMax, dp[i][j]);
}
cout <<endl;
}
return retMax == 2 ? 0 : retMax;
}
};
🥰如果本文对你有些帮助,欢迎👉 点赞 收藏 关注,你的支持是对作者大大莫大的鼓励!!(????) 若有差错恳请留言指正~~
文章来源:https://blog.csdn.net/m0_67470729/article/details/135118641
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!