Algorithm -- climbing stairs (kotlin)

subject

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 ？

 Example  1：

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


 Example  2：

 Input ：n = 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 
 

Tips ：

1 <= n <= 45

https://leetcode.cn/problems/climbing-stairs/

Solutions

1. In fact, the conventional solution of this problem can be divided into several subproblems , Climb the first n The number of ways to step stairs , be equal to 2 The sum of parts
   Climb up n-1 The number of ways to step stairs . Because climb again 1 You can get to the third level n rank
   Climb up n-2 The number of ways to step stairs , Because climb again 2 You can get to the third level n rank
   So we get the formula dp[n] = dp[n-1] + dp[n-2]
   At the same time, you need to initialize dp[0]=1 and dp[1]=1d
   Time complexity ：O(n)

2. since dp[n] = dp[n-1] + dp[n-2]
Then we can use sliding array to solve it

resolvent

    fun climbStairs(n: Int): Int {
    

        val intArray = IntArray(n + 1)
        intArray[0] = 1
        intArray[1] = 1
        for (i in 2..n) {
    
            intArray[i] = intArray[i - 1] + intArray[i - 2]
        }
        return intArray[n]
    }

    fun climbStairs2(n: Int): Int {
    
        var q = 1
        var p = 1
        var result = 1
        for (i in 2..n) {
    
            result = q + p
            q = p
            p = result
        }
        return result
    }

summary

1. I didn't figure out how to do this problem
I read the solution of the problem before I worked it out