面试10- I. 斐波那契数列【动态规划经典】
题目描述
解题思路
方法一：自上而下的递归+记忆化方法
$$ F(0) = 0 \ F(1) = 1 \ F(N) = F(N - 1) + F(N - 2), 其中 N > 1. $$
但是F(4) = F(2) + F(3) ，而 F(3) = F(2)+F(1)。F(2) 被计算了2次，一旦N变的很大，F(2)会被不停的重复计算。
方法二：自下而上的动态规划
斐波那契数列的定义就是我们的动态规划方程
-
初始状态 $F(0) = 0 ,F(1) = 1 $
-
转移方程 $F(N) = F(N - 1) + F(N - 2)$
代码
方法一：递归
class Solution:
def fib(self, n: int) -> int:
def dfs(n):
if n in memo: return memo[n]
memo[n] = dfs(n - 1) + dfs(n - 2)
return memo[n]
memo = {0:0, 1:1}
return dfs(n) % 1000000007
方法二：动态规划
class Solution:
def fib(self, n: int) -> int:
if n == 0: return 0
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n] % 1000000007