跳至主要內容

70. 爬楼梯


70. 爬楼梯open in new window

🟢   🔖  记忆化搜索 数学 动态规划  🔗 力扣open in new window LeetCodeopen in new window

题目

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. 1 step + 1 step

  2. 2 steps

Example 2:

Input: n = 3

Output: 3

Explanation: There are three ways to climb to the top.

  1. 1 step + 1 step + 1 step

  2. 1 step + 2 steps

  3. 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) = 1dp(2) = 2

复杂度分析

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