跳台阶（C++算法）

跳台阶 描述

  一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：1≤n≤40

要求：时间复杂度：O(n) ，空间复杂度： O(1)

示例1

输入：
2
返回值：
2
说明：
青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2 

示例2

输入：
7
返回值：
21

思路/解法 方式一

动态规划。

class Solution {
public:
    int jumpFloor(int number) 
    {
        //将只有一步的过滤掉
        if(number == 1)return 1;
        //从第二步开始
        int preSteps = 1;//preSteps表示上一步位置有多少种跳法，0 1
        int curSteps = 2;//curSteps表示当前位置有多少种跳法，0 1 2 和 0 2
        //状态转移方程：step_i = step_i-1 = step_i-2;i表示当前位置，i-1表示上一步位置，i-2表示上上一步位置，step表示当前步有多少种跳法
        for(int i = 3;i <= number;i++)
        {
            int temp = curSteps;
            curSteps += preSteps;
            preSteps = temp;
        }
        return curSteps;
    }
};

方式二

根据分析，如果使用动态规划，其状态转移方程为：step_i = step_i-1 = step_i-2，实际上这个是斐波那契数列，即f(n) = f(n-1) + f(n-2)。

class Solution {
public:
    int jumpFloor(int number) 
    {
        if(number <= 2)
            return number;
        return jumpFloor(number - 1) + jumpFloor(number - 2);
    }
};