【LeetCode】509. 斐波那契数
2024-09-07 03:22:20
题目
斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N,计算 F(N)。
示例 1:
输入:2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2:
输入:3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3:
输入:4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3.
提示:
0 ≤ N ≤ 30
思路:动态规划
如果使用递归f[n] = f[n-1] + f[n-2]会有大量重复计算,时间复杂度为O(n^2),使用动态规划使时间复杂度为O(n)。
代码
时间复杂度:O(n)
空间复杂度:O(n)
class Solution {
public:
int fib(int N) {
if (N == 0 || N == 1) {
return N;
}
int f[N+1];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= N; ++i) {
f[i] = f[i-1] + f[i-2];
}
return f[N];
}
};
优化空间复杂度
因为每个当前值只与前面两个数相关,所以可以利用两个变量优化空间复杂度。
时间复杂度:O(n)
空间复杂度:O(1)
class Solution {
public:
int fib(int N) {
if (N == 0 || N == 1) {
return N;
}
int a = 0, b = 1;
int res = 0;
for (int i = 2; i <= N; ++i) {
res = a + b;
a = b;
b = res;
}
return res;
}
};
最新文章
- Android安全开发之WebView中的地雷
- 茎叶图(stem)
- C# TreeView的CheckBox 父/子节点点击联动选择效果
- Linux系统下Apache2.4.17的安装过程
- hdu 1052 (greedy algorithm) 分类: hdoj 2015-06-18 16:49 35人阅读 评论(0) 收藏
- C迷途指针
- MVC json
- FusionCharts 分类以及各个属性参数列表
- iBATIS 深入分析
- Java框架之spring框架的优点,为什么要学习spring框架
- 【python小工具】linux 低权限密码记录 提权小套路
- python扫描端口脚本
- BZOJ4034 [HAOI2015]树上操作 树链剖分
- spring mvc发送请求404,不能进入处理方法,也不报错
- LA 3213 古老的密码
- android学习之--网格视图(GridView)和图像切换器(ImageSwitcher)
- 1021 docker搭建mysql、网络模式、grid
- videojs做直播、弹幕
- 以太坊go-ethereum客户端查询交易列表(二)
- 我的Android进阶之旅------>解决Android Studio报错:DefaultAndroidProject : Unsupported major.minor version 52.0