上楼梯问题

有个小孩正在上楼梯，楼梯有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)