Daily Algorithm: Stair Climbing Problem

[[433205]]

Suppose you are climbing a staircase. It takes n steps for you to reach the top.

You can climb 1 or 2 steps at a time. How many different ways can you get to the top of the building?

Note: Given n is a positive integer.

Example 1:

 Input: 2
 Output: 2
 Explanation: There are two ways to get to the roof.
 1. 1st order + 1st order
 2. 2nd order

Example 2:

 Input: 3
 Output: 3
 Explanation: There are three ways to climb to the roof.
 1. 1st order + 1st order + 1st order
 2. 1st order + 2nd order
 3. 2nd order + 1st order

Solution: Dynamic Programming

Dynamic Programming (DP) is a strategy for breaking down complex problems into small problems for solution. However, unlike the divide-and-conquer algorithm, which requires each sub-problem to be independent of each other, the sub-problems of dynamic programming are interrelated.

Divide and conquer, as the name suggests, is to divide and conquer. It divides a complex problem into two or more similar sub-problems, and then divides the sub-problems into smaller sub-problems until the smaller sub-problems can be easily solved. When the sub-problems are solved, the solution to the original problem is the combination of the solutions to the sub-problems.

When we use dynamic programming to solve a problem, we need to follow several important steps:

• Defining subproblems
• Implement the parts of the sub-problem that need to be solved repeatedly
• Identify and solve for boundary conditions

Step 1: Define the subproblems

If we use dp[n] to represent the number of options for the nth step, and we know from the question that the last step may be 2 steps or 1 step, then the number of options for the nth step is equal to the number of options for the n-1th step plus the number of options for the n-2th step.

Step 2: Implement the sub-problems that need to be solved repeatedly

 dp[n] = dp[n−1] + dp[n−2]

Step 3: Identify and solve for boundary conditions

 // Level 0, 1st option
 dp[0]=1
 // Level 1 is also 1 solution
 dp[1]=1

The last step: translate the tail code into code and handle some edge cases

 let climbStairs = function (n) {
 let dp = [1, 1]
 for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
 }
 return dp[n]
 }

Complexity analysis:

• Time complexity: O(n)
• Space complexity: O(n)

Optimize space complexity:

 let climbStairs = function (n) {
    let res = 1, n1 = 1, n2 = 1
 for (let i = 2; i <= n; i++) {
 res = n1 + n2
 n1 = n2
 n2 = res
 }
 return res
 }

Space complexity: O(1)

leetcode: https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-wen-ti-by-user7746o/