This is the 27th day of my participation in the August Genwen Challenge.More challenges in August

70. Climb the stairs

The question:

Suppose you’re climbing stairs. It takes n steps to get to the top.

You can climb one or two steps at a time. How many different ways can you climb to the top?

Note: given n is a positive integer.

Example 1: Input: 2 Output: 2 Description: There are two ways to climb to the top of the building.

  1. 1 order plus 1 order
  2. 2 order

Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top of the building.

  1. 1 order plus 1 order plus 1 order
  2. 1 order plus 2 order
  3. 2 order plus 1 order

Problem solving:

Problem one: recursion

The recursive analysis starts at the first level

The number of statistics in the outermost layer, traversal to the end of a layer is added once

This recursive implementation is timed out in Leetcode, which is obviously not enough, so it’s just a mental exercise

 class Solution {
     int count = 0;
     public int climbStairs(int n) {
         calCount(n);
         return count;
     }
 ​
     public void calCount(int remain){
         if(remain == 0){
             count++;
             return;
         }
 ​
         if(remain > 0){
             calCount(remain - 1);
         }
 ​
         if(remain > 1){
             calCount(remain - 2); }}}Copy the code

Talking to a friend about the above recursive implementation, he said that the above method is not very formal, and the count is outside

This is optimized in a traditional recursive fashion

Note that the remain-2 case is handled here. The solution is that remain < 0 no longer counts and returns the number 0, indicating that this method is invalid

 public int calCount2(int remain) {
     if (remain == 0) {
         return 1;
     } else if (remain < 0) {
         return 0;
     }
​
     return calCount2(remain - 1) + calCount2(remain - 2);
 }
Copy the code
Solution two: dynamic programming

Scenarios where problems need to be analyzed,

If need climbs 9 floors, so the means to 9 floors has two kinds, one kind is from 7 floors directly 9 floors, another kind is from 8 floors to 9 floors, namely the method of 9 floors is equal to the method of 7 floors + to the method of 8 floors

 public int climbStairs(int n) {
     if(n == 1) {return 1;
     }
     int[] array = new int[n];
     array[0] = 1;
     array[1] = 2;
     for(int i = 2; i < n; i++){
         array[i] = array[i-1] + array[i-2];
     }
​
     return array[n-1];
 }
Copy the code