解题（GoUpstairs -- 上楼梯）

题目描述

有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶、3阶。请实现一个方法，计算小孩有多少种上楼的方式。为了防止溢出，请将结果Mod 1000000007

给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100000。

测试样例：

1

返回：1

代码如下：

 //对于上k级台阶,当k>3时，由于每次可以上1,2,3级，则最后一次应该是上1,2,3中的一个

 //case1，最后一次上1级，也即前面上了k-1级，k-1级的可能情况为：A[k-1]次

 //同理 case2,A[k-1], case3 A[k-3]

 //从而有： A[k] = A[k-3] + A[k-2] + A[k-1]

 class GoUpstairs {

 public:

     int countWays(int n) {

         long long resMid;

         long long frontWay[3] = { 1, 2, 4 };

         if (n < 4) return frontWay[n - 1];

         for (int i = 3; i < n; i++){

             long long temp = frontWay[0] + frontWay[1] + frontWay[2];

             frontWay[0] = frontWay[1];

             frontWay[1] = frontWay[2];

             frontWay[2] = temp;

             if (frontWay[2] > 1000000007){

                 frontWay[2] = frontWay[2] % 1000000007;

             }

         }

         int res = frontWay[2] % 1000000007;

         return res;

     }

 };

 借鉴自牛客网友  原文链接：https://www.nowcoder.com/questionTerminal/7f0661ace6df48d0af3f924950d57126