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

分析：

因为好久没有练习思维还没有转变，所以这道题思考有点慢

首先还是建立状态，到达第i级台阶时，有f[i]种跳法

最后答案f[n-1]

再状态转移，f[i]=f[i-1]+f[i-2] 

赋初值，因为可以选择跳一阶或者两阶，所以初始赋值f[0]和f[1]，f[0]=1,f[1]=2

然后编写代码，但是最后有个问题，不知道1e9+7不是整型，所以答案错了

所以先将其转化为整型，最后输出取模

代码：

 1 class Solution(object):
 2     def numWays(self, n):
 3         """
 4         :type n: int
 5         :rtype: int
 6         """
 7         # 跳上第i级台阶共有f[i-1]种跳法
 8         # f[i]=f[i-1]+f[i-2]
 9         # f[n-1]
10         if n==0:
11             return 1
12         if n<=2:
13             return n
14         f=[0 for i in range(n)]
15         f[0]=1
16         f[1]=2
17         for i in range(2,n):
18             f[i]=f[i-1]+f[i-2]
19         # return f[n-1]%1000000007
20         x=int(1e9+7)
21         return f[n-1]%x