题⽬描述
⼀只⻘蛙⼀次可以跳上1 级台阶,也可以跳上2级……它也可以跳上n级。求该⻘蛙跳上⼀个n级的台阶总共有多少种跳法。
思路及解答
数学归纳法
⾸先⻘蛙⼀次可以跳 1 , 2 , 3 到 n 级。假设函数是f(n) ,则:
- ⻘蛙跳到第⼀级是f(1)=1 ,只有⼀种跳法。
- ⻘蛙跳到第⼆级,可以是直接跳到第⼆级,也可以是从第⼀级直接跳。所以f(2)=f(1)+1
- ⻘蛙跳到第三级,可以从第0 级跳,也可以从第1级跳,也可以从第2 级跳。所以f(3)=f(1)+f(2)+1 ;
- 依次类推,⻘蛙跳到第n 级,可以是从0 , 1 , 2 , 3 .. (n-1) 级跳,所以f(n)=f(1)+f(2)+f(3)…+f(n-1)+1 ;
进一步观察可以发现:
- f(1) = 1
- f(2) = f(1) + f(0) = 2
- f(3) = f(2) + f(1) + f(0) = 4
- f(4) = f(3) + f(2) + f(1) + f(0) = 8
显然,这是一个等比数列,通项公式为f(n) = 2^(n-1)。这个发现将问题简化为简单的幂次计算
public class Solution {
public int JumpFloorII(int target) {
if (target <= 0) return 0;
return (int) Math.pow(2, target - 1);
}
}
- 时间复杂度:O(1),直接计算幂次
- 空间复杂度:O(1),仅使用常数空间
数学归纳法的优势在于将问题转化为已知的数学公式,但需要较强的数学观察能力才能发现其中的规律
递归
将大问题分解为小问题来解决。对于n级台阶,青蛙第一次跳跃可以有n种选择:跳1级、跳2级,…,跳n级。如果第一次跳1级,剩下n-1级有f(n-1)种跳法;如果第一次跳2级,剩下n-2级有f(n-2)种跳法;依此类推,直到第一次直接跳n级,有1种跳法。
因此,递归公式为: f(n) = f(n-1) + f(n-2) + … + f(1) + 1
而f(n-1) = f(n-2) + … + f(1) + 1
两式相减可得:f(n) = 2*f(n-1),
public class Solution {
public int JumpFloorII(int target) {
if (target <= 0) return 0;
if (target == 1) return 1;
return 2 * jump(target - 1);
}
}
- 时间复杂度:O(n),需要n次递归调用
- 空间复杂度:O(n),递归调用栈深度为n
递归解法虽然代码简洁,但当n较大时会出现栈溢出风险,且存在大量重复计算,效率较低
动态规划
根据递归分析,我们已经知道f(n)=2*f(n-1)。因此,可以从f(1)开始,逐步计算f(2), f(3), …, f(n),每次利用前一次的结果
动态规划可以将问题分解为重叠的子问题,并存储子问题的解。
初始化:
- f(1) = 1
- 递推关系:f(n) = 2 * f(n-1) for n > 1
这种方法避免了递归的重复计算,通过迭代方式自底向上构建解
public class Solution {
public int JumpFloorII(int target) {
if (target <= 0) return 0;
int[] dp = new int[target + 1];
dp[1] = 1;
for (int i = 2; i <= target; i++) {
dp[i] = 2 * dp[i - 1];
}
return dp[target];
}
}
- 时间复杂度:O(n),单层循环
- 空间复杂度:O(n),需要dp数组存储中间结果
动态规划是递归解法的优化版本,适合大规模输入
优化的动态规划:优化空间复杂度
观察动态规划解法,发现计算f(n)只需要前一个状态f(n-1),不需要保存整个dp数组。因此可以用单个变量代替数组,实时更新当前值。
这种优化基于”滚动数组”思想,只保留必要的中间结果,可以将空间复杂度从O(n)降到O(1)。
public class Solution {
public int JumpFloorII(int target) {
if (target <= 0) return 0;
int result = 1;
for (int i = 2; i <= target; i++) {
result *= 2;
}
return result;
}
}
- 时间复杂度:O(n),单层循环
- 空间复杂度:O(1),仅使用常数空间
这是最优的迭代解法,应该也是面试官最想要看到的解法。