509、斐波那契数

发表于 分类于 ， ， ， 阅读次数： 本文字数： 571 阅读时长 ≈ 1 分钟
简介：LeetCode第509题：斐波那契数

题目

https://leetcode-cn.com/problems/fibonacci-number/

斐波那契数，通常用 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
3
int fib(int n){

}

我的解答

关键代码

1
2
3
4
5
6
int fib(int n){
	if(n==0||n==1){
		return n;
	}
	return fib(n-1)+fib(n-2);
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>

int fib(int n){
	if(n==0||n==1){
		return n;
	}
	return fib(n-1)+fib(n-2);
}

main(){
	int n;
	scanf("%d",&n);
	printf("--%d--",fib(n));
}

复杂度分析

执行用时：12 ms, 在所有 C 提交中击败了28.33%的用户

内存消耗：5.6 MB, 在所有 C 提交中击败了8.92%的用户