70. 爬楼梯
70. 爬楼梯
🟢 🔖 记忆化搜索
数学
动态规划
🔗 力扣
LeetCode
题目
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)
,其中n
是到达楼顶的台阶数量。虽然使用了递归,但通过使用哈希表map
存储已经计算过的结果,确保每个状态只计算一次。因此,最多会计算n
次,整体时间复杂度为O(n)
。 - 空间复杂度:
O(n)
,主要的空间消耗来自于哈希表map
,其存储了从1
到n
的所有计算结果。此外,递归调用栈的深度也可能达到O(n)
,但主要的空间复杂度来源于map
。因此,整体空间复杂度为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);
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
509 | 斐波那契数 | [✓] | 递归 记忆化搜索 数学 1+ | 🟢 | 🀄️ 🔗 |
746 | 使用最小花费爬楼梯 | [✓] | 数组 动态规划 | 🟢 | 🀄️ 🔗 |
1137 | 第 N 个泰波那契数 | [✓] | 记忆化搜索 数学 动态规划 | 🟢 | 🀄️ 🔗 |
2244 | 完成所有任务需要的最少轮数 | 贪心 数组 哈希表 1+ | 🟠 | 🀄️ 🔗 | |
2320 | 统计放置房子的方式数 | 动态规划 | 🟠 | 🀄️ 🔗 | |
2400 | 恰好移动 k 步到达某一位置的方法数目 | 数学 动态规划 组合数学 | 🟠 | 🀄️ 🔗 | |
2466 | 统计构造好字符串的方案数 | 动态规划 | 🟠 | 🀄️ 🔗 | |
2498 | 青蛙过河 II | 贪心 数组 二分查找 | 🟠 | 🀄️ 🔗 | |
3154 | 到达第 K 级台阶的方案数 | 位运算 记忆化搜索 数学 2+ | 🔴 | 🀄️ 🔗 | |
3183 | 达到总和的方法数量 🔒 | 数组 动态规划 | 🟠 | 🀄️ 🔗 |