青蛙跳台阶问题：从递归到动态规划的算法优化

1. 问题描述与初步理解

青蛙跳台阶问题是一个经典的递归算法练习题，题目描述很简单：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。问青蛙跳上一个n级的台阶总共有多少种跳法？

我第一次接触这个问题是在学习动态规划的时候。当时觉得这不过是个数学题，直到真正动手实现时才发现其中蕴含着算法设计的精髓。这个问题的魅力在于它可以用多种思路解决，从最直观的递归到优化的动态规划，再到更高级的数学方法，每种解法都能给我们不同的启发。

2. 递归解法：最直观的思路

2.1 基础递归实现

当我们面对n级台阶时，青蛙的最后一步只有两种可能：

• 跳1级台阶：那么前面n-1级台阶有f(n-1)种跳法
• 跳2级台阶：那么前面n-2级台阶有f(n-2)种跳法

因此，总跳法数就是这两种情况的和：f(n) = f(n-1) + f(n-2)

这实际上就是斐波那契数列的定义。我们可以很容易写出递归代码：

python复制def jump_ways(n):
    if n <= 1:
        return 1
    return jump_ways(n-1) + jump_ways(n-2)

2.2 递归解法的问题

虽然递归解法简单直观，但它存在严重的效率问题。计算f(5)时，我们需要计算f(4)和f(3)；计算f(4)又需要计算f(3)和f(2)...这样会产生大量重复计算。

时间复杂度是指数级的O(2^n)，当n较大时（比如n=50），这个算法几乎无法在合理时间内完成。

提示：在实际面试中，如果只给出递归解法而不指出其问题，通常不会得到满分。

3. 记忆化递归：优化重复计算

3.1 引入记忆化技术

为了优化递归解法，我们可以使用记忆化技术（Memoization），即把已经计算过的结果保存起来，避免重复计算。

python复制def jump_ways_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return 1
    memo[n] = jump_ways_memo(n-1, memo) + jump_ways_memo(n-2, memo)
    return m