题目
爬楼梯问题，这是一道很有趣的问题。首先看题目：
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?
1.递归（对应代码climbStairs）
如果楼梯有n层，我们回退到n-2和n-1步的时候，发现climbStairs(n)=climbStairs(n-1)+climbStairs(n-2)。
为什么？因为当还剩两步的时候，有两种情况，走一个2步，或两个1，但是其中一种情况和climbStairs(n-1)有重复，所以得到如上式子。
这种方法的效率较差，leetcode不接受
2.折中算法（对应代码climbStairs3）
通过上面的讲解，其实只要是任意拆分n为n1，n2和n1+1,n2-1两项就可以。climbStairs(n)=climbStairs(n1)*climbStairs(n2)+climbStairs(n1-1)*climbStairs(n2+1)
这种算法效率最优
3.直接算（对应代码climbStairs1）
k代表1的个数，k从0~n。算出每种情况情况的1步和2步的个数，然后通过牛顿公式算法。但是阶乘较大的时候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的数量
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));
}
}
/********************************
* 本文来自博客 “李博Garvin“
* 转载请标明出处:http://blog.csdn.net/buptgshengod
******************************************/
