斐波那契数，通常用 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fibonacci-number
参考：
python
# 0509.斐波那契数列
class Solution:
def fib(self, n: int) -> int:
"""
递归， 时间O(2^n), 空间O(n)
:param n:
:return:
"""
if n < 2:
return n
return self.fib(n-1) + self.fib(n-2)
class Solution1:
def fib(self, n: int) -> int:
"""
动态规划的简化版
:param n:
:return:
"""
if n < 2:
return n
a,b,c = 0, 1, 0
for i in range(1, n):
c = a + b
a, b = b, c
return c
class Solution2:
def fib(self, n: int) -> int:
"""
动态规划
- 1.确定dp数组
- 2.递推
- 3.dp初始化
- 4.遍历顺序
- 5.举例推到
:param n:
:return:
"""
if n < 2: return n
dp = [0] * 2
dp[0] = 0
dp[1] = 1
for i in range(1, n):
sum = dp[0] + dp[1]
dp[0] = dp[1]
dp[1] = sum
return dp[1]
if __name__ == "__main__":
test = Solution2()
print(test.fib(4))
golang
package dynamicPrograming
// 递归
func fib(n int) int {
if n < 2 {
return n
}
return fib(n-1) + fib(n-2)
}
// 动态规划写法
func fib2(n int) int {
if n < 2 {
return n
}
var sum int
dp := [2]int{}
dp[0], dp[1] = 0, 1
for i:=1;i<n;i++ {
sum = dp[0] + dp[1]
dp[0] = dp[1]
dp[1] = sum
}
return dp[1]
}
// 动态规划的简化写法
func fib3(n int) int {
if n < 2 {
return n
}
var sum int
var a, b int = 0, 1
for i:=1;i<n;i++ {
sum = a + b
a = b
b = sum
}
return sum
}