LeetCode 70. Climbing Stairs 爬楼梯问题

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

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

 

Constraints:

• 1 <= n <= 45

解法一：

使用动态规划求解。这个问题实际上跟求解斐波那契数列是一个问题，假设梯子有n层，那么如何爬到第 n 层呢，因为每次只能爬 1 或 2 步，那么爬到第n层的方法要么是从第 n-1 层一步上来的，要不就是从 n-2 层 2 步上来的，所以递推公式非常容易的就得出了：dp[n] = dp[n-1] + dp[n-2]。代码如下：

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]
    }
}

解法二：

使用动态规划求解，且仅使用三个整型进一步优化空间。

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
    }
}

解法三：

递归加记忆数组求解。普通递归的写法会超时，但是只要加上记忆数组，那就不一样了，因为记忆数组可以保存计算过的结果，这样就不会存在重复计算了，大大的提高了运行效率，其实递归加记忆数组跟迭代的 DP 形式基本是大同小异的，参见代码如下：

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]
        }
    }
}

解法四：

Discuss 上还有一种分治法 Divide and Conquer 的解法，用的是递归形式。

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)
        }
    }
}

解法五：

其实斐波那契数列是可以求出通项公式的，推理的过程请参见 知乎上的这个贴子，那么有了通项公式后，直接在常数级的时间复杂度范围内就可以求出结果了，参见代码如下：

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