题目
假设你正在爬楼梯。需要 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$级台阶的总方法数的函数为$f(n)$,那么递推关系为$f(n)=f(n-1)+f(n-2)$。
- 时间复杂度:$O(2^N)$,空间复杂度$O(N)$。
动态规划
其实也是对暴力法直接递归的优化,存储已经计算过的结果使时间复杂度降为$O(N)$。
代码:
1 | class Solution { |
其实还可以优化,因为计算的窗口大小实际上只有3,我们只需保存三个值即可。
- 时间复杂度$O(N)$,空间复杂度$O(N)$;
1 | class Solution { |
- 时间复杂度$O(N)$,空间复杂度$O(1)$;
再写个递归的动态规划吧!
1 | class Solution { |
写法也是维护一个保存计算值的数组,并对较小的n初始化。
- 时间复杂度$O(N)$,空间复杂度$O(N)$。
数学方法
- 使用矩阵计算斐波那契数列
- 使用斐波那契公式
这些都算是背公式了,先不讨论。