青蛙跳台阶java · 算法深度攻略
⚡ 从递归到动态规划,覆盖网民最关心的〈变态跳台阶〉〈大数台阶〉及面试变种。
📌 青蛙跳台阶问题本质
一只青蛙一次可以跳上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演进时间轴
网友们还关心:〈青蛙跳台阶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>。
- 〈青蛙跳台阶java面试题〉常出现在阿里、字节等大厂。
- 〈青蛙跳台阶递归树〉帮助理解重叠子问题。
- 〈青蛙跳台阶最小花费〉是力扣746题,使用动态规划。
- 〈青蛙跳台阶矩阵快速幂〉实现O(log n)复杂度。
📐 大数台阶 · 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) |