剑指 Offer 10- II. 青蛙跳台阶问题

in with 0 comment

剑指 Offer 10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:2
示例 2:

输入:n = 7
输出:21
示例 3:

输入:n = 0
输出:1

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

一共有 n 个台阶,设一共有 f(n) 种跳法,如果跳 1 个台阶,则剩下 n - 1 个台阶即 f(n - 1) 个跳法,如果跳 2 个台阶,则剩下 n - 2 个台阶即 n - 2 个跳法。总跳法为两种可能性的和,由此可得:f(n) = f(n - 1) + f(n - 2)。

所以这道题还是一个斐波那契数列,与此不同的是,n = 2 时跳法为两种,即 f(0) = 1 和 f(1) = 1

代码

代码同 https://blog.linuxzw.com/archives/%E5%89%91%E6%8C%87%20Offer%2010-%20I:%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97

只需要修改 f(0) = 1 即可