【LeetCode每日一题】剑指 Offer 10- II. 青蛙跳台阶问题（持续更新）2021/5/30今日题目（剑指Offer系列）

60 阅读 0 评论 40 点赞

我是靠谱客的博主微笑向日葵，最近开发中收集的这篇文章主要介绍【LeetCode每日一题】剑指 Offer 10- II. 青蛙跳台阶问题（持续更新）2021/5/30今日题目（剑指Offer系列），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

不要自卑，去提升实力
互联网行业谁技术牛谁是爹
如果文章可以带给你能量，那是最好的事！请相信自己
加油o~

2021/5/30

今日题目（剑指Offer系列）

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

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例：

示例 1：
输入：n = 2
输出：2

示例 2：
输入：n = 7
输出：21

示例 3：
输入：n = 0
输出：1

解题思路：

>本题目是个动态规划问题，只需要找到转移方程
>我们想象青蛙跳最后一次时，会有两种跳法
>一种是跳1阶，另外一种是跳2阶
>在跳1阶这种情况下，青蛙已经跳了n-1阶，那他前n-1阶跳法就是f(n-1)
>对应2阶的情况下，青蛙跳了n-2阶，那他前n-2阶跳法就是f(n-2)
>所以对应总共n阶情况就是两种情况的加和
>f(n)=f(n-1)+f(n-2)

>这就转化成了斐波那契数列，但是本问题中f(0)=1,f(1)=1

Python解法：

class Solution:
    def numWays(self, n: int) -> int:
        if n<=1:
            return 1
        else:
            first=1
            second=1
            
            for i in range(n-1):
                temp=first
                first=second
                second=(second+temp)%(1e9+7)
            return int(second)

Java解法：

class Solution {
    public int numWays(int n) {
        if(n<=1) {
			return 1;
		}
		
		else {
			double first=1;
			double second=1;
			
			for(int i=0;i<n-1;i++) {
				double temp=first;
				first=second;
				second=(second+temp)%(1e9+7);
			}
			
			return (int)second;
		}
    }
}