刷题 爬楼梯 递归 回溯 动态规划

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

点击上方蓝字关注我，我们一起学编程
欢迎小伙伴们分享、转载、私信、赞赏。

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

题目描述：

一个台阶总共有 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 <bits/stdc++.h>
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 test
jincheng@#:$ ./test
correct

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

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

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

int climb_dp(int n)
{
    vector<int> 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];
}

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

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