题目难度: 简单
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。
示例 1:
- 输入：n = 3
- 输出：4
- 说明: 有四种走法
示例 2:
- 输入：n = 5
- 输出：13
提示:
- n 范围在[1, 1000000]之间
题目思考
- 第 n 阶台阶的跳法数目可以根据什么得出?
解决方案
思路
- 这个题目非常类似之前剑指 Offer 系列的青蛙跳台阶问题(链接), 只是将那道题目中的只能跳 1 或 2 阶扩展成了可以跳 1 到 3 阶, 感兴趣的同学可以先看看那篇文章, 然后举一反三, 尝试自己解答
- 分析题目, 每次要么跳 1 级, 要么跳 2 级, 也就是相邻台阶之间的关系非常明确, 可以尝试动态规划的思路
- 转移方程: 对于第 n 阶台阶来说, 它可以从 n-1 阶跳 1 级得到, 也可以由 n-2 阶跳 2 级得到, 还可以由 n-3 阶跳 3 级得到, 这三种方案最后跳到的台阶各不相同, 所以没有任何重合部分, 自然第 n 阶的跳法数目就是 n-1 阶, n-2 阶和 n-3 阶的跳法数之和
- 初始化: 因为用到了 n-1, n-2, n-3, 所以初始化需要考虑前三个台阶:
- 如果有 1 阶台阶, 只能选择跳 1 级, 对应 1 种方案;
- 如果有 2 阶台阶, 可以选择跳两个 1 级, 或者一次性跳 2 级,对应 2 种方案;
- 如果有 3 阶台阶, 可以选择跳 3 个 1 级, 或者先跳 1 级再跳 2 级, 或者先跳 2 级再跳 1 级, 再或者一次性跳 3 级,对应 4 种方案;
- 下面代码对应的就是上面整个过程, 并加入了必要的注释, 方便大家理解
复杂度
- 时间复杂度 O(1): 需要遍历整个数组一遍
- 空间复杂度 O(1): 只使用了几个常数空间的变量
代码
Python 3
class Solution:
def waysToStep(self, n: int) -> int:
# dp, dp[n] = dp[n-1]+dp[n-2]+dp[n-3]
# 为了节省空间可以只使用3个变量, 分别代表跳到当前台阶-2阶, -1阶以及当前台阶的方法数
# 初始化为1,2,4, 分别代表跳到1,2,3级台阶的方法数
dp = [1, 2, 4]
mod = 1000000007
if n <= 3:
return dp[n - 1]
for _ in range(4, n + 1):
# 从第4阶开始循环, 假设当前台阶为i, 那么它可以由i-1台阶跳1级得到 (dp[2]), 也可以由i-2台阶跳2级得到 (dp[1]), 还可以由i-3台阶跳3级得到 (dp[0])
# 所以当前台阶方法数就等于跳到前面三种台阶的方法数之和取模, 然后将原dp[1]赋值给新dp[0], 原dp[2]赋值给新dp[1], 新计算的当前台阶方法数赋值给新dp[2]即可
dp[0], dp[1], dp[2] = dp[1], dp[2], (dp[0] + dp[1] + dp[2]) % mod
# 最终结果显然是dp[2], 代表跳到台阶n的方法数
return dp[2] 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号