剑指offer-9-变态跳台阶

题⽬描述

⼀只⻘蛙⼀次可以跳上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),仅使用常数空间

这是最优的迭代解法,应该也是面试官最想要看到的解法。