有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶、3阶。请实现一个方法，计算小孩有多少种上楼的方式。为了防止溢出，请将结果Mod 1000000007
给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100000。
测试样例：
1
返回：1
把暴力递归变成动态规划
class GoUpstairs:
"""动态规划"""
def countWays(self, n):
mat = [1, 1, 2]
if n<3:
return mat[2]
count = 2
while(count!=n):
count += 1
buff = (mat[count-1]+mat[count-2]+mat[count-3])%1000000007
if buff > 1000000007:
buff = buff%1000000007
mat.append(buff)
return mat[count]
class GoUpstairs:
"""暴力递归"""
def countWays(self, n):
if n==1 or n==0:
return 1
if n==2:
return 2
return self.countWays(n-1)+self.countWays(n-2)+self.countWays(n-3)
