友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
509. Fibonacci Number
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.Given N, calculate F(N).
Example 1:
Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.Example 2:
Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.Example 3:
Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.Note:
0 ≤ N ≤ 30.
思路分析
动态规划
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
* Memory Usage: 36.3 MB, less than 5.51% of Java online submissions for Fibonacci Number.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-04-25 22:06
*/
public int fib(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int i1 = 0;
int i2 = 1;
for (int i = 2; i <= n; i++) {
if (i1 <= i2) {
i1 += i2;
} else {
i2 += i1;
}
}
return Math.max(i1, i2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-21 17:30:28
*/
public int fib(int n) {
int a = 0, b = 1, sum;
for (int i = 0; i < n; i++) {
sum = a + b;
a = b;
b = sum;
}
return a;
}