LeetCode每日一题--爬楼梯

前言

昨天尝试了第一个动态规划题目—可被三整除的最大和，用了全量递归和动态规划两种方案。今天的打卡题目也依旧是一个动态规划题。可能很多人在做动态规划的时候，爬楼梯都是他们做的第一个题。但是这个解法也依然有趣。今天依然从递归和dp两个角度来解题。

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

1
2
3
4
5

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

1
2
3
4
5
6

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

如果看过昨天的可被三整除的最大和，应该很容易就能发现，如果那个题是进阶版本的话，这个顶多算一个初级版。
现在依然采用同样的思路，假设我到了第 n 个台阶，那么我有可能是从 n-1 台阶上来，也有可能是从 n-2 台阶上来。

如果把 n 阶的方案总数记为 f(n) ,那 n-1 和 n-2 的总数就分别为 f(n-1) 和 f(n-2) 。根据上面的分析，不难看出 f(n) = f(n-1) + f(n-2) 。这里要保证定义域有意义，所以最小的 n-2 >=1。
能得到 n∈[3,无穷) ，n=N* 。我们这时候穷举一下小于3的时候， n=1 时，从 0 到 1 只有一种场景， n=2 时，从 0 到 2 有两种场景，即一次直接两步或者一次一步。

现在看一下递归思路的代码:

1
2
3
4
5
6
7
8
9

class Solution {
    public int climbStairs(int n) {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

下面我们来优化这段代码，在已经得知 f(n) = f(n-1) + f(n-2) ，且f(1) = 1, f(2) = 2的条件下，我不难得到 f(3) = f(1) + f(2) 。如果我们把 f(1) 存入一个临时变量 temp1 ，f(2) 存入一个临时变量 temp2 ，f(3) = temp1 + temp2 ，此时再对结果做处理让 f(2) 占据 temp1 ， f(3) 占据 temp2。那一直到最后f(n) = temp1 + temp2。

最终代码

在上一个暴力递归代码稍稍改动之后，最终代码这样优化之后时间复杂度只有O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int climbStairs(int n) {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        int temp1 = 1, temp2 = 2, f_n = 3;
        for (int i = 3; i < n; ++i) {
            temp1 = temp2;
            temp2 = f_n;
            f_n = temp1 + temp2;
        }
        return f_n;
    }
}

总结

我也是刚开始接触动态规划这一类算法题，但是动态算法给我的感觉都是如果不考虑效率的情况下，暴力递归都是可以实现的。至于如何优化递归，我最近做的几题都是找准 n 与 n-1 之间的状态，再反过来从 1->n ，利用数组或者临时变量或者其他数据结构存储信息，从而降低时间复杂度。继续加油！

• ← Previous Post
• Next Post →

...

...

00:00

00:00