专栏首页码上积木LeetCode题解—青蛙跳台阶

LeetCode题解—青蛙跳台阶

前言

今天聊个经典题目:青蛙跳台阶问题

题目

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

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

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

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

题解

假设 n 级的台阶共有f(n)种跳法,那么共有两种情况可以跳到第n级:

  • 1、在n-1级台阶地方,跳一步到n级台阶
  • 2、在n-2级台阶地方,跳两步到n级台阶

所以得出, f(n) = f(n-1) + f(n-2)。

所以这题其实就是一道斐波那契数列。

斐波那契数列我们就熟悉了啊,之前专门写过一篇。

我们可以得出第一种解法:递归

解法1

public int numWays(int n) {
        if(n==0)return 1;
        if(n<3)return n;
        int first=numWays(n-1) % 1000000007;
        int second=numWays(n-2)% 1000000007;
        return (first+second)% 1000000007;
    }

还是老问题,这种递归会有大量重复计算。

比如f(5)=f(4)+f(3),f(4)=f(3)+f(2),f(3)计算了两次。

所以我们将它优化下,对于已经计算过的数值存储起来。

解法2

记忆化递归方法,用数组memo存储已经计算过的数值。

class Solution {
    private int[] memo;

    public int numWays(int n) {
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return jump(n);
    }

    private int jump(int n) {
        if (memo[n] != -1) {
            return memo[n];
        }
        if (n == 1 || n == 0) {
            return 1;
        }
        memo[n] = (jump(n - 1) + jump(n - 2)) % 1000000007;
        return memo[n];
    }
}

时间复杂度

O(n)

空间复杂度

O(n)

解法3

有没有更好的解法呢?可以发现在这个问题中,每次计算得出的结果又可以被下一个台阶所利用,并得出新的结果。

比如f(5)要用到f(4)和f(3)的结果,f(4)又可以被f(6)所利用。

这种大问题可以被解析成小问题,并且小问题的结果可以被重复调用的情况,就可以用到 动态规划算法

还是贯彻f(n) = f(n-1) + f(n-2)的公式,用一个数组进行存储结果,可以得出初步的动态规划解法:

    public int numWays(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 2] + dp[i - 1]) % 1000_000_007;
        }
        return dp[n];
    }

时间复杂度

O(n)

空间复杂度

O(n)

解法4

还能不能优化呢?

其实这个数组可以不用,使用两个变量存储结果,每次存储新的结果就可以,因为每次都只需要上两个结果。

public int numWays(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int pre = 1, cur = 2;
        for (int i = 3; i <= n; i++) {
            int tmp = (pre + cur) % 1000_000_007;
            pre = cur;
            cur = tmp;
        }
        return cur;
    }

用pre和cur两个变量代替了之前的数组dp,每次计算完下一个值之后,也就是tmp=pre+cur。

再次对pre和cur重新赋值,如此反复,最终完成计算。

这种解法的空间复杂度就能优化为O(1)。

参考

https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

感谢大家的阅读,有一起学习的小伙伴可以关注下公众号—码上积木❤️ 每日一个知识点,建立完整体系架构。

本文分享自微信公众号 - 码上积木(Lzjimu),作者:积木zz

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-03-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 青蛙跳台阶问题

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

    用户1149564
  • 92 - 青蛙跳台阶

    若尘_
  • 青蛙跳台阶的问题——Fibonacci

    这几天正在复习算法,今天在看一篇文章时偶然看到这个题目,想了一下居然没什么思路……(抱歉,实在太菜。),文章中提示了一个关键词:Fibonacci 数列。然后我...

    mzlogin
  • 面试题(1):青蛙跳台阶

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

    天道Vax的时间宝藏
  • 看一遍就理解:动态规划详解

    我们刷leetcode的时候,经常会遇到动态规划类型题目。动态规划问题非常非常经典,也很有技巧性,一般大厂都非常喜欢问。今天跟大家一起来学习动态规划的套路,文章...

    PHP开发工程师
  • 看一遍就理解:动态规划详解

    我们刷leetcode的时候,经常会遇到动态规划类型题目。动态规划问题非常非常经典,也很有技巧性,一般大厂都非常喜欢问。今天跟大家一起来学习动态规划的套路,文章...

    烂猪皮
  • 看一遍就理解:动态规划详解

    我们刷leetcode的时候,经常会遇到动态规划类型题目。动态规划问题非常非常经典,也很有技巧性,一般大厂都非常喜欢问。今天跟大家一起来学习动态规划的套路,文章...

    捡田螺的小男孩
  • 台阶很高,青蛙跳不跳?

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

    WindWant
  • 剑指offer第8题:青蛙跳台阶

    根据题意,我们可以看出整个题目的思路是十分清晰的。我们需要想办法将题目语言,先转化为数学符号,最后再转化为编程语言就十分方便了。下面我们来分析一些这道题目。

    鹏-程-万-里
  • 青蛙跳台阶问题(递归练习)

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

    RAIN7
  • 剑指Offer LeetCode 面试题10- II. 青蛙跳台阶问题

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

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

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

    Vincent-yuan
  • 【leetcode刷题】T159-爬楼梯

    https://leetcode-cn.com/problems/climbing-stairs/

    木又AI帮
  • 告别动态规划,连刷40道动规算法题,我总结了动规的套路

    对于动态规划,春招秋招时好多题都会用到动态规划,一气之下,再 leetcode 连续刷了几十道动态规划的题

    乔戈里
  • 动态规划

    假如只差一步就能走完整个台阶,要分为几种情况?因为每一步能走一级或者两级台阶,所以有如下两种情况:

    故事尾音
  • 【leetCode】青蛙跳台问题(这只青蛙会托马斯大旋转)day07

    https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

    居士
  • 告别动态规划,连刷40道动规算法题,我总结了动规的套路

    动态规划难吗?说实话,我觉得很难,特别是对于初学者来说,我当时入门动态规划的时候,是看 0-1 背包问题,当时真的是一脸懵逼。后来,我遇到动态规划的题,看的懂答...

    帅地
  • [剑指offer] 变态跳台阶

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

    尾尾部落
  • 剑指offer(07-09)题解

    思路解析 这一题与上述的那一题大同小异,只要注意一些小问题,显然该题的状态转换方程也和上题差不多,但是这题,有一个不同的地方就是,他不仅可以跳一步,两步,他还...

    萌萌哒的瓤瓤

扫码关注云+社区

领取腾讯云代金券