This is the first day of my participation in Gwen Challenge

The original problem

Climb the stairs

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 Explanation: There are two ways to climb to the top of the building. 1. 1 + 1 + 2. 2Copy the code

Example 2:

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

jolt

Climbing stairs, the legendary classic dynamic planning topic, simple difficulty, suitable for heavy attack.

So let’s define the boundary conditions

  • When n < 1, res = 0;
  • When n = 1, res = 1;

When n is greater than 1, we need to derive the state transition equation, which is the most important step;

state

There are n steps. Let’s say we’re at the end. So if you go up the previous step, depending on the question, you can climb one or two steps, and there are two ways to go:

  1. Take a staircase
  2. Take two stairs

So obviously, n steps is the sum of n minus 1 steps plus n minus 2 steps;

Assuming that DP [n] is the way of n steps, it can be concluded according to the above scheme:


d p [ n ] = d p [ n – 1 ] + d p [ n – 2 ] ; dp[n]=dp[n-1]+dp[n-2];

Now, this is the transition equation;

  • When n < 1, dp[0] = 0
  • When n = 1, dp[1] = 1
  • Dp [n]=dp[n-1]+dp[n-2]

This can be coded as the equation:

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

And then, it turns out that this looks like a Fibonacci sequence.

This code, while correct, takes up a lot of space because there is a lot of double counting of elements in the DP array. Such as:

 dp[20] = dp[19] + dp[18]
 dp[19] = dp[18] + dp[17]
 dp[18] = dp[16] + dp[17]
Copy the code

So, you have to do space optimization, and it’s easy to see that this thing dp[n] only needs to use the first two Spaces of the current space, so you can create two variables and just keep adding them

Replace n-2 moves with dp0, and n-1 moves with dp1.

    public int climbStairs(int n) {
        int dp0=0,dp1=1,res=0;
        for(int i = 1; i <= n; i++) {
            res = dp0 + dp1;
            dp0 = dp1;
            dp1 = res;
        }
        return res;
    }
Copy the code

So, this is a more suitable solution.