IT 面试题库

LeetCode 70 爬楼梯:一次可走 1 或 2 阶,n 阶共有多少种走法?写出状态转移与两种实现。

初级编程题算法工程师Java后端工程师动态规划爬楼梯递推

题目

考察点:DP 入门——把问题拆成『最后一步』得到递推式,并理解自顶向下(记忆化)与自底向上两种写法及空间优化。

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 65 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

思路:到第 n 阶的走法 = 到第 n-1 阶(再走 1 步)+ 到第 n-2 阶(再走 2 步),即经典斐波那契。

要点(状态定义与转移):

# 滚动变量优化空间
def climb(n):
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b if n >= 2 else a

要点(复杂度与注意):

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题