509. 斐波那契数
一、题目描述
斐波那契数，通常用 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
二、解题思路 & 代码
2.1 动态规划 （ O ( n ) O(n) O(n)空间）
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]
print(dp)
return dp[-1]
2.2 动态规划 （ O ( 1 ) O(1) O(1)空间）
相对上面的 O ( n ) O(n) O(n) 空间的做法，唯一的区别就是把一维存储列表变成两个指针，pre 和 cur， 并且循环的次数之间照抄上面的，所以可以先写上面的 O ( n ) O(n) O(n) 做法，确定好循环次数，再做相应的改变即可。
- 初始化 pre 和 cur 的值
- cur 的值先保存在 tmp 中（因为对它操作以后，它之前的那个值就找不回来了）
- cur 进行加的操作
- pre 也后移一位
class Solution:
def fib(self, N: int) -> int:
if N==0:
return 0
pre = 0
cur = 1
for i in range(2, N+1):
tmp = cur
cur = pre + cur
pre = tmp
return cur
================================================
================================================
【剑指offer 10-II】青蛙跳台阶
一、题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
提示：
0 <= n <= 100
二、解题思路 & 代码
class Solution:
def numWays(self, n: int) -> int:
if n == 0 or n == 1:
return 1
dp = [1] * (n+1)
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n] % 1000000007
京公网安备 11010502036488号