題目

思路：題目中只能跨越一步或者兩步，行進(jìn)過程類似于1與2的組合
首先通過n的大小，確定跨越2步的上下界，然后通過高中數(shù)學(xué)有關(guān)組合的知識(shí)可計(jì)算方案數(shù)量。
例如：n=5，5/2=2…1，取到2步的方案如下
0個(gè)2 : 1 1 1 1 1
1個(gè)2 : 1 1 1 2
2個(gè)2 : 1 2 2
再根據(jù)組合，分別計(jì)算累加得出結(jié)果。

書寫演示

關(guān)鍵在計(jì)算組合數(shù)階乘過程中溢出的處理，此處僅僅使用ret=retnume/deno（ret：結(jié)果，nume=n-j：分子，deno=j+1：分母，不使用ret=nume/deno是因?yàn)橛?jì)算過程會(huì)出現(xiàn)不整除的情況）在n=45時(shí)，ret*nume仍會(huì)溢出，于是尋找ret與deno的最大公因數(shù)提前將ret的值變小，抑制溢出的可能

執(zhí)行效率
執(zhí)行用時(shí): 0 ms ,在所有 C提交中擊敗了 100.00%的用戶內(nèi)存消耗: 5.3 MB ,在所有 C提交中 擊敗了94.79%的用戶

代碼如下

bool Divi(int n,int m){//驗(yàn)證整除性return n==n/m*m; }int SearM(int n,int m){//尋找最大公因數(shù)int i=n>m?m:n;for(i;i>0;i--){if(Divi(n,i) && Divi(m,i)){break;}}return i; }int Comb(int n,int i){//組合數(shù)int ret=1,Mf;for(int j=0;j<i;j++){if(Divi(ret,j+1)){ret=ret/(j+1)*(n-j);continue;}Mf=SearM(ret,j+1);ret=(ret/Mf*(n-j))/((j+1)/Mf);}return ret; }int climbStairs(int n){int Sum=0;for(int i=n/2;i>=0;i--){Sum+=Comb(n-i,i);}return Sum; }

總結(jié)

以上是生活随笔為你收集整理的爬楼梯（Leetcode）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。