題目
一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階膳汪。求該青蛙跳上一個 n 級的臺階總共有多少種跳法唯蝶。答案需要取模 1e9+7（1000000007），如計(jì)算初始結(jié)果為：1000000008遗嗽，請返回 1粘我。
例：
輸入：n = 7
輸出：21
方法：動態(tài)規(guī)劃
思路同 劍指 Offer 10- I. 斐波那契數(shù)列
- 根據(jù)題目，青蛙跳上 0 和 1 階臺階均只有一種方法
- dp[i] 表示青蛙跳上第 i 階臺階的方法數(shù)量
- mod 表示取模的值
- 遍歷臺階數(shù)痹换，直至跳到最后一個臺階 n
- 有兩種跳臺階的可能性征字，一次跳一級，和一次跳兩級娇豫。那么想要跳至第 i 級臺階有兩種方法：先跳至第 i-1 級臺階匙姜，再跳一級；先跳至第 i-2 級臺階冯痢，再跳兩級氮昧。方法數(shù)量同理
class Solution(object):
def numWays(self, n):
if n <= 1:
return 1
dp = [1] * (n+1)
dp[1] = 1
mod = 10 ** 9 + 7
for i in range(2, n+1):
dp[i] = (dp[i-1] + dp[i-2]) % mod
return dp[-1]
