这里写代码片// 某编程网站上编程练习题，遇到的问题汇总 2017年2月15日 1、题目描述：上阶梯 有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶、3阶。请实现一个方法， 计算小孩有多少种上楼的方式。为了防止溢出，请将结果Mod 1000000007 给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100000。 我的解决方法：
“` int countWays(int n) { if(n==1){return 1;} if(n==2){return 2;} if(n==3){return 4;} if(n>3){ return countWays(n-1)+ countWays(n-2)+countWays(n-3);} }
测试不通过，因为运行时间不达标。因为，每次计算countWays(n)都需要重新计算前面的countWays(n-1)+countWays(n-2)+countWays(n-3); 就是说计算countWays(5)、countWays(6)等每次都需要重新算。方法一，用数组，数组里面的值，每计算一次，就有了，会保存下来，所以计算了countWay(4)后就不需要计算了，每次都只需要计算新的一个值。另外需要注意，数组类型如果是int ，要防止其越界。递归这个玩意，到底什么时候用呢？ 困惑中下面是用迭代数组的方式进行的： int countWays(int n) { long long a[10000]; if(n<0){return 0;} a[0]=1; a[1]=2; a[2]=4; for(int i=3;i<=n-1;i++) { a[i] = ((a[i-1]+ a[i-2])%1000000007+a[i-3])%1000000007; } return a[n-1];如下的方法也可以:class GoUpstairs { public: int countWays(int n) { // write code here int f1=1; int f2=2; int f3=4; int result=0; if(n<=0) return 0; if(n==1) return 1; if(n==2) return 2; if(n==3) return 4; for(int i=4;i<=n;i++) { result=((f3+f2)%1000000007+f1)%1000000007; f1=f2; f2=f3; f3=result; } return result; } }; “`
新闻热点
疑难解答
图片精选
