题目
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,
1 | F(0) = 0, F(1) = 1 |
Given N
, calculate F(N)
.
Example 1:
1 | Input: 2 |
Example 2:
1 | Input: 3 |
Example 3:
1 | Input: 4 |
Note:
0 ≤ N
≤ 30.
解法1[Java]:递归
1 | class Solution { |
时空复杂度
时间复杂度:
空间复杂度:
解法2[Java]:
1 | class Solution { |
时空复杂度
时间复杂度:$O(n)$
空间复杂度:$O(1)$
解法3[Java]:
1 |