9. 變態(tài)跳臺(tái)階

題目描述

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

解題思路：

• 思路1: 利用遞歸思路，可參考8、跳臺(tái)階
  遞歸公式為：

f(1) = 1
f(2) = 1 + f(1) = 2
f(3) = 1 + f(1) + f(2) = 4
...
f(n) = 1 + f(1) + f(2) + ... + f(n-1)

另外可以觀察到：

f(n) = 1 + f(1) + f(2) + ... + f(n-2) + f(n-1)
f(n-1) = 1 + f(1) + f(2) + ... + f(n-2) + f(n-1)
-->
f(n) = 2*f(n-1)

• 思路2: 除最后一個(gè)臺(tái)階外，每一個(gè)臺(tái)階都可以選擇跳或者不跳，故f(n) = 2 ^ (n - 1)

解答：

// 解法1:
class Solution {
public:
    int jumpFloorII(int number) {
        if(number <= 0)
            return 0;
        if(number == 1)
            return 1;
        int ans = 1;
        while(number > 0)
        {
            ans += jumpFloorII(number -1);
            --number;
        }
        return ans;
    }
};

// 解法2:
class Solution {
public:
    int jumpFloorII(int number) {
        if(number <= 0)
            return 0;
        if(number == 1)
            return 1;
        int ans = 1;
        return 2 * jumpFloorII(number - 1);
    }
};

// 解法3:
class Solution {
public:
    int jumpFloorII(int number) {
        int ans =  pow(2, number - 1);
        return ans;
    }
};

大家有興趣可以訪問(wèn)我的個(gè)人博客，不定時(shí)更新一些內(nèi)容哦！

圖片來(lái)自必應(yīng)壁紙