題目

爬樓梯問題，這是一道很有趣的問題。首先看題目：

You are climbing a stair case. It takes?n?steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

這道題一共有三個方法實現(xiàn)（我想到的）：
1.遞歸（對應(yīng)代碼climbStairs）
如果樓梯有n層，我們回退到n-2和n-1步的時候，發(fā)現(xiàn)climbStairs(n)=climbStairs(n-1)+climbStairs(n-2)。 為什么？因為當(dāng)還剩兩步的時候，有兩種情況，走一個2步，或兩個1，但是其中一種情況和climbStairs(n-1)有重復(fù)，所以得到如上式子。 這種方法的效率較差，leetcode不接受

2.折中算法（對應(yīng)代碼climbStairs3）
通過上面的講解，其實只要是任意拆分n為n1，n2和n1+1,n2-1兩項就可以。climbStairs(n)=climbStairs(n1)*climbStairs(n2)+climbStairs(n1-1)*climbStairs(n2+1) 這種算法效率最優(yōu)

3.直接算（對應(yīng)代碼climbStairs1）
k代表1的個數(shù)，k從0~n。算出每種情況情況的1步和2步的個數(shù)，然后通過牛頓公式算法。但是階乘較大的時候int型會溢出

代碼

package No70.ClimbingStairs;public class Solution {public static int climbStairs(int n) {if(n<=0) return 0;if(n-3>0){return climbStairs(n-2)+climbStairs(n-1);}else{if(n==3) return 3;else {if (n==2){return 2;}else{return 1;}}}}public static int climbStairs1(int n) {if (n==0) return 0;int k=0;//1的數(shù)量int climbNum=0;boolean[] isHas=new boolean[n+1];while(k<=n){int i=(n-k)%2;int j=(n-k)/2;if(isHas[k+i]==false){climbNum+=c_cal(j+i+k,i+k);}isHas[k+i]=true;k++;}return climbNum;}public static int c_cal(int a,int b){if(b==0) return 1;int c1=1;int c2=1;for(int i=0;i<b;i++){c1=c1*(a-i);c2=c2*(b-i);}System.out.print(a+":"+b+" ");return c1/c2; }public static int climbStairs3(int n) { if(n <= 3){ return n; } else{return climbStairs3(n/2)*climbStairs3(n-n/2)+climbStairs3(n/2-1)*climbStairs3(n-n/2-1);}}public static void main(String[] args){System.out.print(""+climbStairs3(50));} }
代碼下載：https://github.com/jimenbian/GarvinLeetCode

/********************************

* 本文來自博客 ?“李博Garvin“

* 轉(zhuǎn)載請標(biāo)明出處:http://blog.csdn.net/buptgshengod

******************************************/

總結(jié)

以上是生活随笔為你收集整理的【LeetCode从零单排】No70.ClimbingStairs的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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