這里寫代碼片// 某編程網站上編程練習題，遇到的問題匯總 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; } }; “`
新聞熱點
疑難解答
圖片精選
