Leetcode.com/problems/cl…

Discuss:www.cnblogs.com/grandyang/p…

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

 

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Copy the code

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Copy the code

 

Constraints:

  • 1 <= n <= 45

Solution a:

Solve using dynamic programming. This is actually the same problem as solving the Fibonacci sequence, assuming the ladder has n levels, how do you get to the NTH level, because you can only climb one or two steps at a time, so the way to get to the NTH level is either one step from the n-1 level, or two steps from the N-2 level, So the recursion formula is very easy: dp[n] = dp[n-1] + dp[n-2]. The code is as follows:

class Solution {
    fun climbStairs(n: Int): Int {
        val topArray = IntArray(size = n + 1)
        topArray[0] = 1
        topArray[1] = 1

        for (i in 2..n) {
            topArray[i] = topArray[i - 1] + topArray[i - 2]}return topArray[n]
    }
}
Copy the code

Method 2:

Dynamic programming solution is used, and only three integer types are used to further optimize the space.

class Solution { fun climbStairs(n: Int): Int { var oneStepBefore = 1 var twoStepBefore = 1 var allWays = 1 for (i in 2.. n) { allWays = oneStepBefore + twoStepBefore twoStepBefore = oneStepBefore oneStepBefore = allWays } return allWays } }Copy the code

Method 3:

Recursively plus memory array solution. The ordinary recursive method will timeout, but as long as plus a memory array, it won’t be the same, because the memory array can store the results calculated, so as not to duplicate calculation, greatly improved the operation efficiency, actually recursive add memory array with iterative DP basic is pretty much the same form, see the HTML code is as follows:

class Solution {
    fun climbStairs(n: Int): Int {
        val topArray = IntArray(n + 1)
        return helper(n, topArray)
    }

    private fun helper(n: Int, topArray: IntArray): Int {
        if (n <= 1) return 1
        return if (topArray[n] > 0) {
            topArray[n]
        } else {
            topArray[n] = helper(n - 1, topArray) + helper(n - 2, topArray)
            return topArray[n]
        }
    }
}
Copy the code

Method 4:

There is also a Divide and Conquer solution on Discuss, which is recursive.

class Solution {
    fun climbStairs(n: Int): Int {
        return if (n <= 1) {
            1
        } else {
            climbStairs(n / 2) * climbStairs(n - n / 2) + climbStairs(n / 2 - 1) * climbStairs(n - n / 2 - 1)
        }
    }
}
Copy the code

Method 5:

In fact, the Fibonacci sequence can be derived from the general term formula. Please refer to this post on Zhihu for the reasoning process. Then with the general term formula, the results can be directly obtained within the range of constant time complexity, as shown in the code below:

class Solution { fun climbStairs(n: Int): Int {val root5 = math.sqrt (5.0) val res = 1 / (math.pow ((1 + root5) / 2, n + 1.toDouble()) - Math.pow( (1 - root5) / 2, n + 1.toDouble() )) return res.toInt() } }Copy the code