算法练习(八):青蛙跳台阶问题

时间:2021-08-26 00:06:04   收藏:0   阅读:20

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

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

示例 1:

输入:n = 2
输出:2

  

示例 2:

输入:n = 7
输出:21

  

示例 3:

输入:n = 0
输出:1

  

解题思路:

设跳上 n 级台阶有 f(n)种跳法。在所有跳法中,青蛙的最后一步只有两种情况: 跳上 1 级或 2 级台阶。

即 f(n) 为以上两种情况之和,即 f(n)=f(n-1)+f(n-2) ,以上递推性质为斐波那契数列。因此,本题可转化为 求斐波那契数列第 n 项的值 , 斐波那契数列 等价,唯一的不同在于起始数字不同。

package Algriothm;

public class Solution3 {

    public static void main(String[] args) {

        int i = numWays(7);
        System.out.println(i);
    }

    public static int numWays(int n) {

       int a = 1, b = 1, sum;
        for (int i = 0; i < n; i++) {
            sum = (a + b) % 100000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

 

技术分享图片

 

原文:https://www.cnblogs.com/yssd/p/15186936.html

评论(0)
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!