Daily Algorithm: Stair Climbing Problem

Dynamic programming (Dynamic Programming, DP) is a strategy for decomposing complex problems into small problems, but unlike the divide-and-conquer algorithm, the divide-and-conquer algorithm requires each sub-problem to be independent of each other, while the sub-problems of dynamic programming are mutually independent. Associated.

Suppose you are climbing stairs. It takes n steps to reach the top of the building.

 

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

 

Note: Given n is a positive integer.

 

Example 1:

1. Input: 2

2. Output: 2

3. Explanation: There are two ways to climb to the top of the building.

4. 1st order + 1st order

5. 2. 2nd order

 

Example 2:

1. Input: 3

2. Output: 3

3. Explanation: There are three ways to climb to the top of the building.

4. 1. 1st order + 1st order + 1st order

5. 2. 1st order + 2nd order

6. 3. 2nd order + 1st order

 

Solution: dynamic programming

Dynamic programming (Dynamic Programming, DP) is a strategy for decomposing complex problems into small problems, but unlike the divide-and-conquer algorithm, the divide-and-conquer algorithm requires each sub-problem to be independent of each other, while the sub-problems of dynamic programming are mutually independent. Associated.

Divide and conquer, as the name implies, is divide and conquer. A complex problem is divided into two or more similar sub-problems, and the sub-problems are divided into smaller sub-problems until the smaller sub-problems can be solved simply and the sub-problems can be solved. Then the solution of the original problem is a combination of the solutions of the sub-problems.

 

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

 

Define subproblems

Realize the sub-sub-problems that need to be solved repeatedly

Identify and solve boundary conditions

 

Step 1: Define sub-problems

If dp[n] is used to represent the number of plans for the nth step, and it is known from the question: the last step may be 2 steps or 1 step, that is, the number of plans for the nth step is equal to the n-1th step The number of plans plus the number of plans for the n-2th step

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

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

 

Step 3: Identify and solve the boundary conditions

1. // Level 0 1 scheme

2. dp[0]=1

3. // Level 1 is also a scheme

4. dp[1]=1

 

The last step: Translate the end code into code and deal with some boundary conditions 

1. let climbStairs = function(n) {

2.   let dp = [1, 1]

3.    for(let i = 2; i <= n; i++) {

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

5.    }

6.    return dp[n]

7. }

Complexity analysis:

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

Optimize space complexity:

1. let climbStairs = function(n) {

2.    let res = 1, n1 = 1, n2 = 1

3.   for(let i = 2; i <= n; i++) {

4.        res = n1 + n2

5.        n1 = n2

6.        n2 = res

7.    }

8.    return res

9. }

Space complexity: O(1)

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