首页 > 试题广场 >

上高楼

[编程题]上高楼
  • 热度指数:4089 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

现在有一栋高楼,但是电梯却出了故障,无奈的你只能走楼梯上楼,根据你的腿长,你一次能走1级或2级楼梯,已知你要走n级楼梯才能走到你的目的楼层,请计算你走到目的楼层的方案数,由于楼很高,所以n的范围为int范围内的正整数。

给定楼梯总数n,请返回方案数。为了防止溢出,请返回结果Mod 1000000007的值。

测试样例:
3
返回:3
头像 _Bingbong
发表于 2024-12-31 23:18:43
解题思路 这是一个斐波那契数列的变种问题,使用矩阵快速幂来解决。关键点: 递推关系: 可以使用矩阵快速幂优化时间复杂度 矩阵转换: 使用 矩阵进行状态转移 注意矩阵下标从 开始 取模运算: 所有运算都需要取模,防止溢出 mod = 1000000007 代码 展开全文

问题信息

难度:
16条回答 10792浏览

热门推荐

通过挑战的用户

查看代码
上高楼