題目

一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階。求該青蛙跳上一個(gè) n 級的臺階總共有多少種跳法。答案需要取模 1e9+7（1000000007），如計(jì)算初始結(jié)果為：1000000008，請返回 1。

例：
輸入：n = 7
輸出：21

方法：動(dòng)態(tài)規(guī)劃

思路同 劍指 Offer 10- I. 斐波那契數(shù)列

• 根據(jù)題目，青蛙跳上 0 和 1 階臺階均只有一種方法
• dp[i] 表示青蛙跳上第 i 階臺階的方法數(shù)量
• mod 表示取模的值
• 遍歷臺階數(shù)，直至跳到最后一個(gè)臺階 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]