动态规划之爬楼梯

爬楼梯的三种题型

基础

question1：
假设你正在爬楼梯。需要n阶才能到达楼顶。
每次可以爬1或2个台阶。有多少种不同的方法可以爬到楼顶？

当我们站在第n层台阶时，只能是由n-1阶或者n-2阶跳上去的。因此我们需要保存到达n-1和n-2级台阶的方法数。不妨设置大小为n+1的数组dp（dynamic programming），其中dp[i]代表到达第i级台阶的方法数。由上可知，有dp[i]=dp[i-1]+dp[i-2]，不难看出此数组即位斐波那契数列。
代码：

void solution1() {
    int n = 0;
    std::cin >> n;

    if (n < 3){
        std::cout << n;// 直接判断
        return;
    }

    long long dp[51] = {}; // 假设最多50级台阶
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    std::cout << dp[n] << std::endl;
    return;
}

由于对于每一个台阶，只需要保存前一级台阶和前两级台阶，因此只需要两个变量的空间即可。

代码：

void solution2() {
    int n = 0;
    std::cin >> n;

    if (n < 3){
        std::cout << n;// 直接判断
        return;
    }
    int pre = 1;
    int prePre = 1;
    int result = 0;

    for (int i = 3; i <= n; i++) {
        result = pre + prePre;
        prePre = pre;
        pre = result;
    }

    std::cout << result << std::endl;
    return;
}

提高

question2：
爬楼梯。
每次可以爬1或2个台阶，并且不能连续跳两次二级台阶，有多少种不同的方法可以爬到楼顶？

由于对两阶的连续性作出了限制，因此我们除了保存跳跃之前在哪一级台阶之外，还需要保存前一次是否跳了两阶。此时不妨设一个二维数组，对于dp[i][j]而言，其中i代表处于第i级台阶，j代表连续跳2阶的次数，由于不能连续跳两级，所以j只能是0或者1，**dp[i][j]就代表连续j次跳了两级台阶后到达第i级台阶的方法数**。最终到第n级台阶的总数就是dp[n][0]+dp[n][1]。对于第i级台阶来说，满足以下关系：

dp[i][0]=dp[i-1][0]+dp[i-1][1];
dp[i][1]=dp[i-2][1];

代码：

void solution3() 
{
    int n = 0;
    std::cin >> n;

    if (n < 3)
    {
        std::cout << n;
        return;
    }

    long long dp[51][2] = {}; //i代表处于第i级台阶，j代表连续跳2阶的次数，由于不能连续跳两级，所以j只能是0或者1，dp[i][j]就代表连续j次跳了两级台阶后到达第i级台阶的方法数，j只能是0或1
    //所以最后返回dp[n][0]+dp[n][1]
    //从dp[i][j]开始，可以有两种情况，一种到dp[i+1][0],因为没有连续两级台阶，一种到dp[i+2][j+1]
    dp[0][0] = 1;
    dp[0][1] = 0;

    dp[1][0] = 1;
    dp[1][1] = 0;

    dp[2][0] = 1;
    dp[2][1] = 1;

    for (int i = 3; i <= n; i++) {
        dp[i][0] = dp[i - 1][0] + dp[i - 1][1]; // 到了第i级台阶，并且之前一次不是两级台阶，则只能是由前一级台阶来的，并且如何到的前一级台阶? 可以有2种情况，分别是0次两级，1次两级
        dp[i][1] = dp[i - 2][0];// 到了第i级台阶，并且之前一次是两级台阶，是由前两级台阶来的，并且如何到的前两级台阶? 唯一情况是之前跳了一级然后到的前两级

    }

    std::cout << dp[n][0] + dp[n][1];
    return;

}

拓展一

question3：
爬楼梯。
每次可以爬1或2个台阶，并且不能连续三次跳两级台阶，有多少种不同的方法可以爬到楼顶？

与第二种情况类似，**dp[i][j]就代表连续j次跳了两级台阶后到达第i级台阶的方法数**，j只能是0，1，或者2。从dp[i][j]开始，可以有两种情况，一种是跳了一级到i+1级，且跳两级台阶的次数为0，即dp[i+1][0],另一种跳了两级，到i+2级台阶，跳两级台阶的次数为j+1，即dp[i+2][j+1] 。

代码：

void sln() {
    int n = 0;
    std::cin >> n;

    if (n < 3)
    {
        std::cout << n;
        return;
    }

    long long dp[51][3] = {}; //二维数组dp的第二维 0 1 2表示的是: dp[i][j] 在第i级台阶，之前是有连续j次走了二级台阶的方法数
    //所以到达第n阶的总方法数就是dp[n][0]+dp[n][1]+dp[n][2]
    //从dp[i][j]开始，可以有两种情况，一种到dp[i+1][0],因为没有连续两级台阶，一种到dp[i+2][j+1]。
    dp[0][0] = 1;
    dp[0][1] = 0;
    dp[0][2] = 0;

    dp[1][0] = 1;
    dp[1][1] = 0;
    dp[1][2] = 0;

    dp[2][0] = 1;
    dp[2][1] = 1;
    dp[2][2] = 0;

    for (int i = 3; i <= n; i++) {
        dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]; // 到了第i级台阶，并且之前一次不是两级台阶，则只能是由前一级台阶来的，并且如何到的前一级台阶? 可以有3种情况，分别是0次两级，1次两级，2次两级
        dp[i][1] = dp[i - 2][0];// 到了第i级台阶，并且之前一次是两级台阶，是由前两级台阶来的，并且如何到的前两级台阶? 为保证最近仅一次跳了两级，唯一情况是跳了一级然后到的前两级
        dp[i][2] = dp[i - 2][1];// 到了第i级台阶，并且之前两次都是两级台阶，是由前两级台阶来的，并且如何到的前两级台阶? 唯一情况是跳了两级然后到的前两级
    }

    std::cout << dp[n][0] + dp[n][1] + dp[n][2];
    return 0;
}

后两种情况也同样可以 用变量代替数组，但是对于理解来说数组更友好，因此没有给出变量版本。

拓展二：最小花费

爬楼梯。
从楼梯第i个台阶向上爬需要支付cost[i]的费用。
一旦你支付此费用，即可选择向上爬一个或者两个台阶。
返回爬到楼顶需要的最小花费。

int sln(vector<int>& cost) {
    auto size = cost.size();
    vector<int> dp(size + 1); 
    // dp[i] 是到第i层后的最小花费，其中包括第i层的花费
    dp[0] = cost[0];
    dp[1] = min(cost[1], cost[0] + cost[1]);

    for(int i = 2; i <= size; i++) {
        dp[i] = (i == size ? 0 : cost[i]) + min(dp[i - 1], dp[i - 2]);
    }
    return dp[size];
}

在上面的解决方法中，将cost[i]放在了min的外面，是因为基于这样的思路：到达第i级台阶后将立刻花费，所以放在外面，只需关注是前一级花费小还是前两级花费小即可。

到达楼顶时，由于超出cost的范围，因此该层花费为0。