今日算法09-青蛙跳台阶问题

一、题目描述

题目链接：leetcode.cn/problems/qi…

难易程度：简单

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

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

示例1

输入：n = 2

输出：2

​

示例2

输入：n = 7

输出：21

​

示例3

输入：n = 0

输出：1

​

​

二、解题思路

动态规划

当 n 为 1 时，只有一种覆盖方法：

​

​

当 n = 2 时，有两种跳法：

​

​

跳 n 阶台阶，可以先跳 1 阶台阶，再跳 n-1 阶台阶；或者先跳 2 阶台阶，再跳 n-2 阶台阶。而 n-1 和 n-2 阶台阶的跳法可以看成子问题，该问题的递推公式为：

​

​

也就变成了斐波那契数列问题，参考：今日算法07-斐波那契数列

复杂度分析

时间复杂度 O(N) ：计算 f(n) 需循环 n 次，每轮循环内计算操作使用 O(1) 。

空间复杂度 O(1) ： 几个标志变量使用常数大小的额外空间。

三、代码实现

public int JumpFloor(int n) {

    if (n <= 2)

        return n;

    int pre2 = 1, pre1 = 2;

    int result = 0;

    for (int i = 2; i < n; i++) {

        result = pre2 + pre1;

        pre2 = pre1;

        pre1 = result;

    }

    return result;

}

推荐阅读

• 
  
• 今日算法07-斐波那契数列
  

封面

今日算法系列，题解更新地址：studeyang.tech/2023/0725.h…