有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶、3阶。请实现一个方法，计算小孩有多少种上楼的方式。为了防止溢出，请将结果Mod 1000000007
给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100000。
测试样例：
1
返回：1
思路：为n时（n大于3）,n可以由n-1的地方跨1步上来，也可以由n-2地方跨2台阶上来，也可以由n-3处跨3阶上来。
注意n-2处与n-3处如果跨一步，就变成了n-1与n-2问题，所以不需要考虑。
故f(n)=f(n-1)+f(n-2)+f(n-3)
非递归代码：
import java.util.*; public class GoUpstairs { public int countWays(int n) { // write code here if(n<=0)return 0; if(n==1)return 1;//1 if(n==2)return 2;//1+1or2 if(n==3)return 4;//1+1+1or1+2,2+1,3 int array[] = new int[n]; array[0]=1;array[1]=2;array[2]=4; for(int i =3;i<n;i++){ //因为array[i-3]在上一轮已经取过模了，每次相加都要取模保证不会溢出。 array[i]=(array[i-3]+(array[i-2]+array[i-1])00000007)00000007; } return array[n-1]; } }
递归代码，开销太大通过不了：
import java.util.*; public class GoUpstairs { public int countWays(int n) { // write code here if(n<=0)return 0; if(n==1)return 1;//1 if(n==2)return 2;//1+1or2 if(n==3)return 4;//1+1+1or1+2,2+1,3 return ((countWays(n-1)+countWays(n-2))00000007+countWays(n-3))00000007; } }