调试中...
简单
相关标签
相关企业
提示
三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。
示例 1：
输入：n = 3 输出：4 说明：有四种走法
示例 2：
输入：n = 5 输出：13
提示:
- n 范围在[1, 1000000]之间
通过次数
79.1K
提交次数
217.3K
通过率
36.4%
相关企业
提示 1
自上而下地处理这个问题。小孩的最后一跳是什么？
提示 2
如果知道跳到第100级台阶之前的每一级台阶的跳法数量，可以计算第100级台阶的跳法数量吗？
提示 3
可以通过步数99、98、97的数量，来计算100步的数量。这对应孩子最后迈1步、2步或3步。我们把它们加起来还是相乘？也就是说，它是f(100) = f(99) + f(98)+ f(97) 或者f(100) = f(99)×f(98)×f(97)吗？
提示 4
当“我们这样做然后那样做”时，将这些值相乘。当“我们这样做或者那样做”时，将这些值相加。
提示 5
这个方法的运行时间是多少？仔细想想。你能优化它吗？
提示 6
尝试用制表法的方式优化效率低下的递归过程。
评论 (0)
《程序员面试金典（第 6 版）》独家授权
本书是原谷歌资深面试官的经验之作，帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的，帮助你轻松应战 IT 名企技术面试。
© 2025 领扣网络（上海）有限公司
0 人在线
行 1，列 1