70. climb stairs

Force button topic link

Suppose you're climbing the stairs . need n You can reach the top of the building .

Every time you climb 1 or 2 A stair . How many different ways can you climb to the top of the building ？

Be careful ： Given n Is a positive integer .

Example 1：

• Input ： 2
• Output ： 2
• explain ： There are two ways to climb to the top .
  • 1 rank + 1 rank
  • 2 rank

Example 2：

• Input ： 3
• Output ： 3
• explain ： There are three ways to climb to the top .
  • 1 rank + 1 rank + 1 rank
  • 1 rank + 2 rank
  • 2 rank + 1 rank

     *  The first stair       1
     *  The second stair       2        11  or   2
     *  The third stair       3        111   12    213
     *  The fourth stair       5        1111  112  121  211  22
     *  The fifth stair       8        11111 1112 1121 1211 122 2111 212 221

Algorithm implementation steps ：

• determine dp The meaning of arrays and subscripts
  – Definition dp[i] To climb the third i How many options are there for steps .
• Determine the state transfer equation
  – Because you can only climb 1 perhaps 2 A stair , therefore , The plan to climb the current level should be the sum of the previous two states , namely dp [ i ] = dp [ i - 1 ] + dp [ i - 2 ]

To understand this wave in depth : dp[i] How to achieve , By dp [ i - 1 ] Move a bit or dp [ i - 1 ] Move two bits to get . The mobile 1 grid All possible and mobile 2 All the possibilities of lattice . Namely dp [ i ] Value . How many in all dp [ i - 1 ] and dp [ i - 2 ] It's possible , Recursion , Or dynamic programming is calculated according to the previous result , It is similar to the result value of each layer of array cache done before .

• Initialization status
  – i = 0 Level is still downstairs , Didn't start climbing
  – i = 1 Level 1 starts climbing , namely dp[1]=1
  – i = 2 level , Yes 2 Kind of ,dp[2]=2
• traversal order
  – From the state transition equation dp[i] yes dp[i-1] and dp[i-2] Turn around , So go from front to back
• Return value
  – The first n Take the stairs and return dp[n]

package com.programmercarl.dynamic;

/** * @ClassName ClimbStairs * @Descriotion TODO * @Author nitaotao * @Date 2022/7/21 8:18 * @Version 1.0 * https://leetcode.cn/problems/climbing-stairs/ * 70.  climb stairs  **/
public class ClimbStairs {
    
    public int climbStairs(int n) {
    
        if (n <= 1) {
    
            return n;
        }
        /** *  The first stair  1 *  The second stair  2 11  or  2 *  The third stair  3 111 12 21 *  The fourth stair  5 1111 112 121 211 22 *  The fifth stair  8 11111 1112 1121 1211 122 2111 212 221 */
        // dp[0] no need 
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        int first = dp[1];
        int second = dp[2];
        for (int i = 3; i <= n; i++) {
    
            // Like Fibonacci series 
            // According to the first two, the third 
            int cur = first + second;
            dp[i] = cur;
            first = second;
            second=cur;
        }
        return dp[n];
    }
}