70. Climbing Stairs
70. Climbing Stairs
题目
You are climbing a staircase. It takes n
steps to reach the top.
Each time you can either climb 1
or 2
steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1 step + 1 step
2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step
Constraints:
1 <= n <= 45
题目大意
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数
解题思路
这是一个经典的动态规划问题,通常被称为「爬楼梯问题」。假设你要爬上第 n 阶楼梯,你可以从第 n-1 阶爬一步上来,也可以从第 n-2 阶爬两步上来,因此到达第 n 阶楼梯的方法数等于到达第 n-1 阶和第 n-2 阶的方法数之和。这样,我们可以得到以下的递推关系:
dp(n) = dp(n - 1) + dp(n - 2)
其中,dp(n)
表示到达第 n 阶楼梯的方法数。
接下来,我们需要初始化边界条件。当 n = 1
时,只有一种方法爬到楼顶;当 n = 2
时,有两种方法爬到楼顶(一步一步或直接两步)。因此,我们可以初始化 dp(1) = 1
和 dp(2) = 2
。
时间复杂度 O(n),空间复杂度 O(n)。
代码
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
let map = new Map();
const helper = (n) => {
if (n <= 2) return n;
if (!map.has(n)) {
map.set(n, helper(n - 1) + helper(n - 2));
}
return map.get(n);
};
return helper(n);
};
相关题目
- [746. 使用最小花费爬楼梯](https://leetcode.com/problems/min-cost-climbing-stairs)
- [509. 斐波那契数](./0509.md)
- [1137. 第 N 个泰波那契数](https://leetcode.com/problems/n-th-tribonacci-number)
- [2244. 完成所有任务需要的最少轮数](https://leetcode.com/problems/minimum-rounds-to-complete-all-tasks)
- [2320. 统计放置房子的方式数](https://leetcode.com/problems/count-number-of-ways-to-place-houses)
- [2400. 恰好移动 k 步到达某一位置的方法数目](https://leetcode.com/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps)
- [2466. 统计构造好字符串的方案数](https://leetcode.com/problems/count-ways-to-build-good-strings)
- [2498. 青蛙过河 II](https://leetcode.com/problems/frog-jump-ii)