剑指OFFER 跳台阶

递归解法

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

二层递归

画出状态图，有点类似二叉树的遍历取叶子结点的个数。

动态规划解法

在写代码之前，先把问题捋清楚

这样就可以写出代码了

class Solution {
    
public:
    vector<int> dp;
    int jumpFloor(int number) {
        dp.resize(number+1);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        int i;
        for(i=3;i<=number;i++)
        {
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[number];
    }
};

剑指OFFER 跳台阶

原文：https://www.cnblogs.com/virgildevil/p/12175602.html