题⽬描述
⼀只⻘蛙⼀次可以跳上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)。这个发现将问题简化为简单的幂次计算
时间复杂度：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)，
时间复杂度：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
这种方法避免了递归的重复计算，通过迭代方式自底向上构建解
时间复杂度：O(n)，单层循环
空间复杂度：O(n)，需要dp数组存储中间结果
动态规划是递归解法的优化版本，适合大规模输入
优化的动态规划：优化空间复杂度
观察动态规划解法，发现计算f(n)只需要前一个状态f(n-1)，不需要保存整个dp数组。因此可以用单个变量代替数组，实时更新当前值。
这种优化基于"滚动数组"思想，只保留必要的中间结果，可以将空间复杂度从O(n)降到O(1)。
时间复杂度：O(n)，单层循环
空间复杂度：O(1)，仅使用常数空间
这是最优的迭代解法，应该也是面试官最想要看到的解法。