JZ69跳台阶

😀前言
青蛙跳台阶是一个经典的问题，它描述了一只青蛙每次可以跳上1级台阶或者2级台阶，问跳上一个n级的台阶有多少种跳法。这个问题看似简单，实则蕴含了一定的数学思维和递推关系。在本文中，我们将通过分析问题的特性和使用动态规划的方法来解决这个问题，并探讨其时间复杂度和空间复杂度的优化。

🏠个人主页：尘觉主页

文章目录

跳台阶
- 题目链接
- 题目描述
- 解题思路
- 😄总结

跳台阶

题目链接

牛客网

描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
数据范围:1 ≤ n ≤ 40
要求:时间复杂度:O(n)，空间复杂度:0(1)

题目描述

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

在这里插入图片描述

解题思路

当 n = 1 时，只有一种跳法：

在这里插入图片描述

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

在这里插入图片描述

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

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;
}

😄总结

通过本文的介绍，我们了解了青蛙跳台阶的问题描述和解题思路。我们发现，该问题可以通过动态规划的方法来解决，通过定义递推公式并进行状态转移，我们可以在O(n)的时间复杂度内解决该问题。同时，我们也分析了问题的时间复杂度和空间复杂度，并提出了一种空间复杂度为O(1)的优化方案。青蛙跳台阶问题虽然简单，但其中蕴含的数学思想和动态规划的思想却具有一定的深度，希望本文对读者有所启发和帮助。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持