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. 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 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入： n = 2

输出： 2

解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶

2. 2 阶

示例 2：

输入： n = 3

输出： 3

解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶

2. 1 阶 + 2 阶

3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

解题思路

1. 递归定义：

   • 设 dp[i] 表示到达第 i 级台阶的方法数。

   • 由于每次只能爬 1 级或 2 级，因此可以从 i-1 或 i-2 级台阶爬上来：

     dp[i] = dp[i - 1] + dp[i - 2]

   • 这与 斐波那契数列 相同。

2. 边界条件：

   • dp[0] = 1（只有一种方式，即不爬）。
   • dp[1] = 1（只能一步到达）。

3. 动态规划求解：

   • 使用数组 dp 记录状态。
   • 递推 dp[i] = dp[i - 1] + dp[i - 2] 直到 dp[n]。

4. 优化点：滚动变量

   • 用两个变量 prev1 和 prev2 代替数组 dp，将空间复杂度优化为 O(1)。

复杂度分析

• 时间复杂度：O(n)，仅需一次循环计算 dp[i]。
• 空间复杂度：
  • O(n)，使用数组 dp。
  • 可优化为 O(1)，仅存 dp[i-1] 和 dp[i-2]。

代码

动态规划

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
	let dp = new Array(n + 1).fill(0);
	dp[0] = 1;
	dp[1] = 1;
	for (let i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
};

动态规划-滚动变量

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
	if (n <= 1) return 1;
	let prev2 = 1,
		prev1 = 1;
	for (let i = 2; i <= n; i++) {
		let curr = prev1 + prev2;
		prev2 = prev1;
		prev1 = curr;
	}
	return prev1;
};

相关题目

题号	标题	题解	标签	难度	力扣
509	斐波那契数	[✓]	递归 记忆化搜索 数学 1+	🟢	🀄️ 🔗
746	使用最小花费爬楼梯	[✓]	数组 动态规划	🟢	🀄️ 🔗
1137	第 N 个泰波那契数	[✓]	记忆化搜索 数学 动态规划	🟢	🀄️ 🔗
2244	完成所有任务需要的最少轮数		贪心 数组 哈希表 1+	🟠	🀄️ 🔗
2320	统计放置房子的方式数		动态规划	🟠	🀄️ 🔗
2400	恰好移动 k 步到达某一位置的方法数目		数学 动态规划 组合数学	🟠	🀄️ 🔗
2466	统计构造好字符串的方案数	[✓]	动态规划	🟠	🀄️ 🔗
2498	青蛙过河 II		贪心 数组 二分查找	🟠	🀄️ 🔗
3154	到达第 K 级台阶的方案数		位运算 记忆化搜索 数学 2+	🔴	🀄️ 🔗
3183	达到总和的方法数量 🔒		数组 动态规划	🟠	🀄️ 🔗