抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

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:这里还有一些高级解法,可在题解中查看。这里只是为了熟悉动态规划。


0条评论

发表评论