leetcode70 climbing stairs 爬樓梯游戲

姘存按發(fā)布于2019-08-14 17:52 / 913人閱讀

摘要：題目要求假設(shè)有級(jí)臺(tái)階為正整數(shù)，每次可以爬一級(jí)臺(tái)階或兩級(jí)臺(tái)階。問(wèn)有多少種方法爬完級(jí)臺(tái)階遞歸方法最后一步可以是一級(jí)臺(tái)階，或者是兩級(jí)臺(tái)階，一共兩種情況。

題目要求：假設(shè)有n級(jí)臺(tái)階（n為正整數(shù)），每次可以爬一級(jí)臺(tái)階或兩級(jí)臺(tái)階。問(wèn)有多少種方法爬完n級(jí)臺(tái)階？

遞歸方法
最后一步可以是一級(jí)臺(tái)階，或者是兩級(jí)臺(tái)階，一共兩種情況。可通過(guò)遞歸獲得n-1級(jí)臺(tái)階和n-2級(jí)臺(tái)階的和獲得n級(jí)臺(tái)階的結(jié)果
臺(tái)階數(shù)量過(guò)高的話，性能會(huì)很差

/**
 * @author rale
 * 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?
 * Note: Given n will be a positive integer.
 */
public class ClimbingStairs {

    //遞歸    
    public int climbStairs(int n) {
        if(n<=1){
            return 1;
        }
        if(n%2==0){
            return (int) (Math.pow(climbStairs(n/2), 2)+Math.pow(climbStairs(n/2-1), 2));
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }
}

非遞歸情況
為了提高性能，將遞歸轉(zhuǎn)化為循環(huán)
可以將題目轉(zhuǎn)換為n級(jí)臺(tái)階中有幾步是爬了兩級(jí)臺(tái)階，幾步是爬了一級(jí)臺(tái)階
例如 3級(jí)臺(tái)階的的場(chǎng)景為 3個(gè)一步或者 1個(gè)一步加1個(gè)兩步
則n級(jí)臺(tái)階的場(chǎng)景為：
假設(shè)n級(jí)臺(tái)階中有a個(gè)兩步，n-2*a個(gè)一步，則情況總數(shù)為C(n-a,a)
a的取值范圍為[0,n/2]

/**
 * @author rale
 * 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?
 * Note: Given n will be a positive integer.
 */
public class ClimbingStairs {
        public int climbStairs(int n){
        if(n<=1){
            return 1;
        }
        int countTwo = 1;
        int total = 1;
        while(countTwo*2<=n){
            //此處應(yīng)設(shè)為long，防止值溢出
            long temp = 1;
            for(int i = n-countTwo, j = 1 ; j<=countTwo; i--,j++){
                temp = temp*i/j;
            }
            total += temp;
            countTwo++;
        }
        return total;
    }
}

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~