📌 青蛙跳台阶问题本质

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。这其实是斐波那契数列的经典应用,也是动态规划的入门必做题。在java实现中,我们通常从递归开始,逐步优化到空间O(1)的迭代。

⚙️ 递推公式

设跳上 n 级台阶有 f(n) 种方法,则:
f(n) = f(n-1) + f(n-2) ,其中 f(1)=1, f(2)=2。

🧠 网民关注点

  • ① 递归如何避免重复计算?
  • ② 动态规划与记忆化搜索区别
  • ③ 大数台阶导致int溢出怎么办?
  • ④ 变态跳台阶(一次跳1~n级)解法

🔄 三种经典java实现

🐢 朴素递归 (指数级复杂度)

直接使用递归公式,但存在大量重复计算,时间复杂度O(2ⁿ)。仅适用于n较小的情况。

public int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return climbStairs(n-1) + climbStairs(n-2);
}

⚠️ 当n=45时,递归耗时已难以接受。网友常搜索「青蛙跳台阶java递归优化」。

🧳 记忆化搜索 (自上而下)

使用数组memo存储已计算值,避免重复。时间复杂度降至O(n)。

int[] memo;
public int climbStairs(int n) {
    memo = new int[n+1];
    return dfs(n);
}
int dfs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (memo[n] != 0) return memo[n];
    memo[n] = dfs(n-1) + dfs(n-2);
    return memo[n];
}

📘 记忆化递归是面试中展示递归优化能力的常用手段。

⚡ 动态规划 (自下而上)

使用迭代方式,空间可优化至O(1)。这是最推荐的青蛙跳台阶java解法。

public int climbStairs(int n) {
    if (n <= 2) return n;
    int first = 1, second = 2;
    for (int i = 3; i <= n; i++) {
        int third = first + second;
        first = second;
        second = third;
    }
    return second;
}

✅ 该解法可轻松应对n=1000(需配合BigInteger处理大数)。

⏳ 青蛙跳台阶java演进时间轴

阶段Ⅰ 暴力递归 → 发现重叠子问题,n>40几乎不可用。
阶段Ⅱ 记忆化递归 → 引入memo数组,时间降至线性。
阶段Ⅲ 动态规划迭代 → 仅用两个变量,空间O(1)。
阶段Ⅳ 矩阵快速幂 → 时间复杂度O(log n),适合极大n。

网友们还关心:〈青蛙跳台阶java大数溢出〉。当n>45时,结果超过int范围,需使用BigInteger或取模运算。

🧬 青蛙跳台阶变种 · 网友热搜

🐸 变态跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求跳上n级台阶的方法数。

f(n) = 2n-1 (n≥1)。使用移位运算:1 << (n-1)。

📊 三步问题

青蛙一次可以跳1级、2级或3级。递推公式:f(n)=f(n-1)+f(n-2)+f(n-3),初始f(1)=1,f(2)=2,f(3)=4。

变种类型递推公式java核心思路
经典跳台阶f(n)=f(n-1)+f(n-2)斐波那契迭代
变态跳台阶f(n)=2*f(n-1)位运算或DP
三步问题f(n)=f(n-1)+f(n-2)+f(n-3)滚动数组
带代价跳台阶dp[i]=min(dp[i-1],dp[i-2])+cost[i]一维DP

❓ 网友们还关心 · 青蛙跳台阶java

🔹 青蛙跳台阶和斐波那契区别?

本质上相同,但初始项不同。斐波那契通常f(0)=0,f(1)=1;而青蛙跳台阶f(1)=1, f(2)=2,对应斐波那契的f(n+1)。

🔸 如何用java打印所有跳法?

使用回溯算法,记录路径。例如n=3时,跳法为〔1,1,1〕〔1,2〕〔2,1〕。需维护List>。

📐 大数台阶 · BigInteger实战

当n=100时,结果已经达到573147844013817084101,必须使用java.math.BigInteger。

import java.math.BigInteger;
public BigInteger climbStairsBig(int n) {
    if (n <= 2) return BigInteger.valueOf(n);
    BigInteger first = BigInteger.ONE;
    BigInteger second = BigInteger.valueOf(2);
    for (int i = 3; i <= n; i++) {
        BigInteger third = first.add(second);
        first = second;
        second = third;
    }
    return second;
}

⚙️ 网友们还关心:模1e9+7的情况,避免大数运算过慢。

📈 复杂度对比一览

方法时间复杂度空间复杂度
朴素递归O(2ⁿ)O(n)
记忆化递归O(n)O(n)
动态规划O(n)O(1)
矩阵快速幂O(log n)O(1)