剑指Offer 10- II. 青蛙跳台阶问题（Easy）

剑指Offer 10- II. 青蛙跳台阶问题（Easy）

【题目链接】

题解

青蛙跳台阶问题（动态规划，清晰图解）

方法

class Solution(object): ### 0904 递归（超时） # def numWays(self, n): # """ # :type n: int # :rtype: int # """ # def recursion(n): # if n == 0 or n == 1: # return 1 # else: # return recursion(n-1) + recursion(n-2) # return recursion(n) ### 0904 记忆化递归 def numWays(self, n): """ :type n: int :rtype: int """ record = {} record[0], record[1] = 1, 1 for i in range(2, n+1): record[i] = (record[i-1] + record[i-2]) % (1e9+7) return int(record[n]) ### 0904 循环求余法 def numWays(self, n): a, b = 1, 1 for _ in range(n): a, b = b, a + b return a % 1000000007