The title

Suppose you are climbing the stairs. It takes you 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 of the building? Note: given n is a positive integer.Copy the code

The sample

Input: 2 Output: 2 Explanation: There are two ways to climb to the top of the building. 1. 1 + 1 2. 2Copy the code

The main idea

  • First define an array dp, where dp[I] indicates that there are dp[I] methods to climb to the ith step
  • And they know that you can climb 1 or 2 steps at a time, so there are two ways to climb the ith step.
  • The first way is to climb 1 step, so you go from i-1 to i-1
  • The second way is to climb 2 steps, so you go from i-2 to i-1
  • So the number of ways to get to step I is the sum of the number of ways to get to step I-1 and the number of ways to get to step I-2
  • Dp [I] = dp[I -1] + dp[I -2]
  • Dp [1] = 1 dp[2] = 2;
  • The array is traversed from front to back

Code implementation

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

Code optimization

public int climbStairs(int n) { if(n <= 2){ return n; } // int a = 1;} // int a = 1; int b = 2; int c = 0; for(int i = 3; i <= n; i++){ c = a + b; a = b; b = c; } return c; }Copy the code

reference

Random code