写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
输入:n = 2
输出:1
输入:n = 5
输出:5
代码:1.递归:(超时)
class Solution:
def fib(self, n: int) -> int:
if n == 0:
return 0
elif n == 1:
return 1
else:
return (self.fib(n-1) + self.fib(n-2))%1000000007
2.记忆化搜索(超时)
class Solution:
def fib(self, n: int) -> int:
table = [-1 for i in range(n+1)]
if n == 0:return 0
if n == 1:return 1
if table[n] == -1:
table[n] = (self.fib(n-1) + self.fib(n-2))%1000000007
return table[n]
3.DP:
class Solution:
def fib(self, n: int) -> int:
table = [0, 1]
for i in range(2,n+1):
table.append((table[i-1] + table[i-2])%1000000007)
return table[n]
剑指 Offer 10- II. 青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
输入:n = 2
输出:2
输入:n = 7
输出:21
输入:n = 0
输出:1
和斐波拉切数列以一个题:只是在f(0)处的初值不一样.到第n级只有两种方式:从n-2级走两步到第n级,或者从n-1级走一步到第n级。假设到第n-2级的方式有 f(n-2)种,到第n-1级的方式有f(n-1)种,则到第n级的方式有:f(n-2)+f(n-1)。
class Solution:
def numWays(self, n: int) -> int:
table = [1, 1]
for i in range(2,n+1):
table.append((table[i-1] + table[i-2]))
return table[-1]%1000000007