本文共 2302 字，大约阅读时间需要 7 分钟。

微信搜索：编程笔记本，获取更多干货知识

点击上方蓝字关注我，我们一起学编程

欢迎小伙伴们分享、转载、私信、赞赏。

今天分享一道字节跳动的面试题：爬楼梯Ⅱ 。

题目描述：

一个台阶总共有 n 级，如果一次可以跳 1 级，也可以跳 2 级，但不能连续两次跳 2 级。求总共有多少总跳法。

分析：

如果没有“不能连续两次跳 2 级”的约束，那么我们很容易写出下面的递归函数：

int climb(int n){
       if (n == 1 || n == 2) {
           return n;    }    return climb(n - 1) + climb(n - 2);}

上面的代码中，势必包括了连续两次跳 2 级的跳法。那么，我们尝试着去除这些多余的跳法。

若要去除这些跳法，我们就要去除连续两次、三次、四次 …… 跳 2 级的跳法，这样一来，势必会将问题变得极其复杂。

我们换一种思路：不能连续两次跳 2 级的意思，换句话说就是跳完 2 级后只能再跳 1 级。那么，我们将“跳完 2 级后再跳 1 级”封装成一个整体—— 3 级。

这样一来，题目就等价于：一个台阶总共有 n 级，如果一次可以跳 1 级，也可以跳 3 级，。求总共有多少总跳法。

我们很容易写出下面这段代码：

微信搜索：编程笔记本，获取更多干货知识

int climb(int n){
       if (n == 1 || n == 2 || n == 3) {
           return n;    }    return climb(n - 1) + climb(n - 3);}

分析到这里，题目就已经求解完成了。为了避免部分小伙伴对这种解法正确性的怀疑，我们用最笨的回溯法来验证一下。

#include 
   
    using namespace std;int climb(int n){
       if (n == 1 || n == 2 || n == 3) {
           return n;    }    return climb(n - 1) + climb(n - 3);}// 回溯法int climb_test(int now, int all, bool jmp2){
       int cnt = 0;    if (now == all) {
       // 抵达终点，数量加一        ++cnt;        return cnt;    }    if (now > all) {
        // 跳多了，直接返回        return cnt;    }    // 未到终点    cnt += climb_test(now + 1, all, false);       // 跳 1 级，并将“跳 2 级”标识复位        if (!jmp2) {
           cnt += climb_test(now + 2, all, true);    // 跳 2 级，并将“跳 2 级”标识置位    }    return cnt;}int main(){
       string info = "correct";        for (int i = 1; i < 50; ++i) {
           int num1 = climb(i);        int num2 = climb_test(0, i, false);        if (num1 != num2) {
               info = "error";            break;        }    }    cout << info << endl;    return 0;}
   

编译运行：

微信搜索：编程笔记本，获取更多干货知识

jincheng@#:$ g++ test.cpp -o testjincheng@#:$ ./testcorrect

可见，我们写的代码是正确的。

其实，递归法是十分消耗资源的一种算法，主要是函数堆栈的动态生成与切换。下面我们使用动态规划法改写递归法的代码。

动态规划其实就是用空间换时间的方法，我们将子问题的解保存下来，这样一来，重复的子问题就只需计算一次，从而优化了算法的时间复杂度。

int climb_dp(int n){
       vector
   
     dp(n+1);    // 保存子问题的解，dp[i] 表示 i 级楼梯的总跳法    dp[1] = 1;              // 初始化    dp[2] = 2;    dp[3] = 3;    for (int i = 4; i <= n; ++i) {
           dp[i] = dp[i - 1] + dp[i - 3];    }    return dp[n];}
   

好啦，今天的内容就到这里！有不明白的小伙伴欢迎私信咨询，我一定知无不言！

微信搜索：编程笔记本，获取更多干货知识