这是一道斐波那契数列的follow-up，所以可以用解决斐波那契数列的方法解决这一题，分析题目，我们发现由于青蛙一次只能跳一步或两部，所以用f（n）来表示青蛙跳到n阶台阶可能的跳法，其运算过程可以表示为f（n）= f（n-1）+ f（n-2）。我们能够轻易地发现这和斐波那契数列的递推公式是相同的，所以可以仿照其，写出代码。算法一中的状态转移过程所用的存储空间不是最优的，故用两个变量进行了优化。最终，这个算法的时间复杂度是O（N），空间复杂度是O（1）。
class Solution:
def numWays1(self, n: int) -> int:
dp = [1] * (n + 1)
for i in range(2, n + 1):
dp[i] = dp[i-1] % 1000000007 + dp[i-2] % 1000000007
return dp[n] % 1000000007
def numWays2(self, n: int) -> int:
a, b = 1, 1
for i in range(0, n):
a, b = b % 1000000007, (a + b) % 1000000007
return a % 1000000007PREVIOUSlc056.合并区间
NEXTlc079.单词搜索