Climbing Stairs（算法）

改了很多溢出的问题之后，发现最优时间也是1ms，而大部分人都是0ms，悲伤之余去看了下别人的解答……

只想说思路很重要。刚开始也想到了，后续的台阶步数是与之前的和有关系的，但是没仔细找……

好吧。就当复习了一下组合数的计算方法，以及溢出的应对办法/(ㄒoㄒ)/~~

题目

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?

My Ugly Code

public class Solution {
    public int climbStairs(int n) {
        if(n<2)
            return 1;
        int  one=0,two = n/2;
        long count = 0;
        if(n%2!=0)
            one = 1;
        //n可以用two个2和one个1表示出来
        //two的范围0~two(p),则one=(two-p)*2
        for(int p=0;p<two+1;p++){
            count = count + myCalc(((two-p)*2+one),p);   //1的个数,2的个数
        }
        return (int)count;
    }
    private long myCalc(int a,int b){
        int sum = a+b;  
        int less = (a>b)?b:a; 
       // System.out.println("sum="+sum+",less="+less);
        if(less==0)
            return 1;
        long retd = 1,ret = 1;
        while(less>0){
            if(sum%less==0){
                ret *= (sum/less);
            }
            else{
                retd *= less;
                ret *= sum;
            }
            //约分公因数，避免溢出
            if(retd%2==0 && ret%2==0){
                retd = retd/2;
                ret = ret/2;
            }
            if(retd%3==0 && ret%3==0){
                retd = retd/3;
                ret = ret/3;
            }
            sum--;
            less--;
        }
       // System.out.println(ret+"/"+retd);
        return ret/retd;
    }
}

Others Genius Code

public class Solution {

public int climbStairs(int n) {
    if(n == 0 || n == 1 || n == 2){return n;}
    int[] mem = new int[n];
    mem[0] = 1;
    mem[1] = 2;
    for(int i = 2; i < n; i++){
        mem[i] = mem[i-1] + mem[i-2];
    }
    return mem[n-1];
}