LeetCode: 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:

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

Example:

Input: n = 4
Output: 5
Explanation: There are five ways to climb to the top:
1. 1 step + 1 step + 1 step + 1 step
2. 1 step + 1 step + 2 steps
3. 1 step + 2 steps + 1 step
4. 2 steps + 1 step + 1 step
5. 2 steps + 2 steps

问题

你正在爬一个楼梯。爬到楼顶需要 n 步。

每次你可以爬 1 步或 2 步。你有多少种不同的方法可以爬到楼顶？

解决方案

动态规划 (DP)

Approach 1: Dynamic Programming (Bottom-Up) / 动态规划（自底向上）

This problem can be solved by recognizing that it is essentially a Fibonacci-like problem. To reach the nth step, you could have come from either the (n-1)th step or the (n-2)th step. Therefore, the number of distinct ways to reach step n is the sum of the distinct ways to reach steps n-1 and n-2.

这个问题可以通过识别它本质上是一个类似于斐波那契的问题来解决。要到达第 n 步，你可以从第 (n-1) 步或第 (n-2) 步走过来。因此，到达第 n 步的不同方法数是到达第 n-1 步和第 n-2 步的方法数之和。

Implementation / 实现

Python

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2

        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2

        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]

Explanation / 解释

1. Base Cases / 基本情况

   if n == 1:
      return 1
   if n == 2:
      return 2

   • English: If n is 1, there is only one way to climb the stairs. If n is 2, there are two ways (either two 1-step moves or one 2-step move).
   • Chinese: 如果 n 是 1，则只有一种方法爬楼梯。如果 n 是 2，则有两种方法（要么两个1步，要么一个2步）。

2. DP Array Initialization / 动态规划数组初始化

   dp = [0] * (n + 1)
   dp[1] = 1
   dp[2] = 2

   • English: We initialize a DP array dp of size n+1. We set the base cases dp[1] = 1 and dp[2] = 2.
   • Chinese: 我们初始化一个大小为 n+1 的动态规划数组 dp。我们设置基本情况 dp[1] = 1 和 dp[2] = 2。

3. Fill DP Array / 填充动态规划数组

   for i in range(3, n + 1):
      dp[i] = dp[i - 1] + dp[i - 2]

   • English: For each step from 3 to n, the number of ways to reach that step is the sum of the ways to reach the previous step and the step before that.
   • Chinese: 对于从第3步到 n 的每一步，到达该步骤的方法数是到达前一步和前两步的方法数之和。

4. Return the Result / 返回结果

   return dp[n]

   • English: After filling the DP array, we return dp[n], which contains the number of ways to reach the nth step.
   • Chinese: 填充动态规划数组后，我们返回 dp[n]，它包含到达第 n 步的方法数。

Approach 2: Optimized Dynamic Programming (Space Optimization) / 动态规划优化（空间优化）

Instead of using an array to store all values, we can optimize the space complexity to O(1) by using two variables to track the last two values.

我们可以通过使用两个变量来跟踪最后两个值，从而将空间复杂度优化为 O(1)，而不是使用数组存储所有值。

Python

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2

        prev1, prev2 = 2, 1

        for i in range(3, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current

        return prev1

Explanation / 解释

1. Track the Last Two Values / 跟踪最后两个值

   prev1, prev2 = 2, 1

   • English: We use two variables prev1 (representing dp[i-1]) and prev2 (representing dp[i-2]) to track the number of ways to reach the last two steps.
   • Chinese: 我们使用两个变量 prev1（表示 dp[i-1]）和 prev2（表示 dp[i-2]）来跟踪到达最后两步的方法数。

2. Update in Each Iteration / 每次迭代时更新

   for i in range(3, n + 1):
      current = prev1 + prev2
      prev2 = prev1
      prev1 = current

   • English: In each iteration, current represents the number of ways to reach step i. We then update prev2 to prev1 and prev1 to current for the next step.
   • Chinese: 在每次迭代中，current 代表到达第 i 步的方法数。然后我们将 prev2 更新为 prev1，将 prev1 更新为 current，以准备下一步。

3. Return the Final Value / 返回最终值

   return prev1

   • English: After the loop finishes, prev1 will contain the number of ways to reach step n.
   • Chinese: 循环结束后，prev1 将包含到达第 n 步的方法数。

Recursive Approach / 递归方法

A recursive solution would involve calculating the number of ways to reach step n by recursively calculating the values for n-1 and n-2. However, this solution is not efficient due to repeated calculations.

递归解决方案涉及通过递归计算 n-1 和 n-2 的值来计算到达第 n 步的方法数。然而，这种解决方案由于重复计算而效率不高。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n) for both DP and optimized DP solutions, as we compute the result in a single pass.
• Space Complexity / 空间复杂度: O(n) for the basic DP solution and O(1) for the optimized DP solution.

Key Concept / 关键概念

• Fibonacci Sequence / 斐波那契数列: The number of ways to reach step n follows a Fibonacci-like sequence where each value is the sum of the previous two values.
• 斐波那契数列: 到达第 n 步的方法数遵循类似于斐波那契数列的规律，每个值是前两个值之和。

Summary / 总结

• English: The Climbing Stairs problem is a classic example of dynamic programming, where we can reduce space complexity by only keeping track of the last two values.
• Chinese

: 爬楼梯问题是动态规划的经典例子，我们可以通过仅跟踪最后两个值来减少空间复杂度。

Tips / 提示

• English: Practice recognizing when problems can be solved using dynamic programming, especially when the solution involves breaking the problem down into smaller subproblems.
• Chinese: 练习识别何时可以使用动态规划解决问题，尤其是当解决方案涉及将问题分解为较小的子问题时。

Solution Template for Similar Questions / 提示

• English: For problems that involve breaking down into subproblems (like Fibonacci sequences), consider using dynamic programming to avoid redundant calculations.
• Chinese: 对于涉及分解为子问题的问题（如斐波那契数列），考虑使用动态规划以避免重复计算。

5 More Similar Questions / 推荐5问题

1. LeetCode 746. Min Cost Climbing Stairs
2. LeetCode 198. House Robber
3. LeetCode 213. House Robber II
4. LeetCode 91. Decode Ways
5. LeetCode 62. Unique Paths

Recommended Resources / 推荐资源

• English: Practice dynamic programming problems to strengthen your ability to identify subproblems and avoid redundant calculations.
• Chinese: 练习动态规划问题，以加强你识别子问题和避免重复计算的能力。

**

7:00 / 18:07

•
Brute Force

Climbing Stairs – Dynamic Programming – Leetcode 70 – Python by NeetCode**