[数据结构与算法]剑指offer 009、跳台阶扩展问题

剑指offer 009、跳台阶扩展问题

题目

题解

很简单，跳到第n个台阶时有f(n) = f(n - 1) + f(n - 2) + … + f(1) = 2 * f(n - 1) 种方法。

// 递归的方法
class Solution {
public:
    int jumpFloorII(int number) {
        if (number == 1) {
            return 1;
        }
        
        return 2 * jumpFloorII(number - 1);
    }
};

// 非递归
class Solution {
public:
    int jumpFloorII(int number) {
        if (number == 1) {
            return 1;
        }
        
        int count = 1;
        for (int i = 2; i <= number; ++i) {
            count *= 2;
        }
        return count;
    }
};

// 直接用pow函数
class Solution {
public:
    int jumpFloorII(int number) {
        if (number == 1) {
            return 1;
        }
        
        return pow(2, number - 1);
    }
};