45 | 面试题：爬楼梯

70. 爬楼梯

解法一：回溯，类似斐波拉契

枚举所有的路径，不断的判断路径是否可以走通。

f [ n ] = f [ n – 1 ] + f [ n – 2 ]
f [ 0 ] = f [ 1 ] = 1

这题用这个解法会超时。

解法二：递归逻辑 + 记忆化 => 动态规划

列出递推公式：f [ n ] = f [ n – 1 ] + f [ n – 2 ]

写一个 for 循环，记忆相邻两位，递推上去。

class Solution {
    fun climbStairs(n: Int): Int {
        if (n <= 1) return n

        var pre = 1
        var cur = 1

        for (i in 2..n) {
            val res = pre + cur
            pre = cur
            cur = res
        }

        return cur
    }
}

解法 N：这里还有一些高级解法，可在题解中查看。这里只是为了熟悉动态规划。