两种方法:

  1. 斐波那契数列(找规律——爬1层1种,2层2种,3层3种,4层5种...)
  2. 动态规划

有必要总结一下找规律的解法:这种解法需要细心和耐心,我们一般取出前3种情况看一下规律,如果规律不明显,可以增加情况,直到过于复杂才放弃此解法。PS:前几种情况同样可以用来检验算法的正确性

动态规划——设dp[i]表示第i层的跳法,状态公式如下:

  1. 如果i>1,dp[i] = dp[i-2] + dp[i-1])
  2. 基准1: dp[0]=0
  3. 基准2: dp[1]=1
  4. 基准3: dp[2]=2

状态公式的解释:

  1. 最后一步跨越一个或两个台阶,因此dp[i] = dp[i-2] + dp[i-1])
  2. 0个阶梯步数为0
  3. 1个阶梯步数为1
  4. 2个阶梯步数为2

为什么会有这么多基准条件呢?因为动态规划的本质是数学归纳法,而数学归纳法对于基准条件是没有限制的,因此基准条件具体应该设置多少个需要我们列举出最前面几种情况,再做一个综合判断

动态规划解法代码如下:

//
// Created by jt on 2020/8/30.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param n int整型
     * @return int整型
     */
    int climbStairs(int n) {
        // write code here
        vector<int> dp(n+1, 0);
        dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i-2] + dp[i-1];
        }
        return dp[n];
    }
};

斐波那契数列解法代码如下:

//
// Created by jt on 2020/8/30.
//
class Solution {
public:
    /**
     *
     * @param n int整型
     * @return int整型
     */
    int climbStairs(int n) {
        // write code here
        int i = 0, j = 1;
        while(n--) {
            int k = i + j;
            i = j;
            j = k;
        }
        return j;
    }
};