福州企业建设网站,成都房地产信息网官网,电子商务网站设计,网络推广都有哪些平台一、题目
一只青蛙一次可以跳上1级台阶#xff0c;也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e97#xff08;1000000007#xff09;#xff0c;如计算初始结果为#xff1a;1000000008#xff0c;请返回 1。
二、示例
2.1也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e971000000007如计算初始结果为1000000008请返回 1。
二、示例
2.1 示例 1 【输入】n 2 【输出】2 2.2 示例 2 【输入】n 7 【输出】21 2.3 示例 3 【输入】n 0 【输出】1 提示
0 n 100
三、解题思路
根据题目描述青蛙只能跳1级台阶或者跳2级台阶那么我们可以针对这个条件演示一下不同台阶青蛙的跳法。比如 对于1阶台阶来说小青蛙只有1种跳法就是向上跳1级对于2阶台阶来说小青蛙有2种跳法分别是向上跳1级然后再跳1级 直接向上跳2级对于3阶台阶来说小青蛙有3种跳法分别是执行3次1级跳 直接向上跳2级再跳1级 先跳1级然后直接向上跳2级对于4阶台阶来说小青蛙有5种跳法分别是执行4次1级跳 2次1级跳再直接跳2级 直接跳2级再执行2次1级跳 1级跳再直接跳2级再执行1次1级跳 执行2次2极跳……针对上面描述我们来看下面图示会更好理解一些 从上面的示例中我们可以看到从1阶到4阶的跳法分别是1种、2种、3种、5种……是不是似曾相识呢是的就是斐波那契数列那为什么会是这样的规律呢下面我们以第n级台阶来看对于它来说往前一步其实只有两种情况 【情况1】在第n-1级处那么只需要向上跳1步即可。 【情况2】在第n-2级处那么只需要向上跳2步即可。 既然是这样我们以f(n)表示到达第n级阶梯的跳法那么可以推理出 f(n) f(n-1) f(n-2) , 所以我们根据推导出的公式关系就可以解出——青蛙跳上一个 n 级的台阶总共有多少种跳法了。 四、代码实现
class Solution {public int numWays(int n) {int a 1, b a, c b, mod (int)1e9 7;for (int i 2; i n; i, a b, b c) c (a b) % mod;return c;}
} 今天的文章内容就这些了 写作不易笔者几个小时甚至数天完成的一篇文章只愿换来您几秒钟的 点赞 分享 。 更多技术干货欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享每天更新」
