经典动态规划问题：爬楼梯的多种解法详解

引言

今天我们要解决一个经典的算法问题——爬楼梯问题。这个问题看似简单，但蕴含了多种解法，从递归到动态规划，再到组合数学，每种方法都有其独特的思路和优化方式。本文将详细讲解四种解法，并通过代码和图解帮助大家深入理解。

问题描述

小兔子喜欢蹦蹦跳跳上楼梯，它能一次跳1阶楼梯，也能一次跳2阶楼梯。问小兔子要上一个n阶的楼梯，最多有多少种不同的上楼走法？

输入输出

• 输入：一个整数n，表示楼梯的阶数。
• 输出：上楼梯的走法数。

解法一：递归解法

思路：
问题可以分解为子问题。假设小兔子要跳到第n阶，那么它最后一步有两种选择：

1. 从n-1阶跳1步到达n阶。
2. 从n-2阶跳2步到达n阶。

因此，总的走法数等于ways(n-1) + ways(n-2)。

代码实现：

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(ways(10));
    }
    static int ways(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        return ways(n-1) + ways(n-2);
    }
}

递归树展示了ways(10)的调用过程，可以看到大量的重复计算。

解法二：记忆化递归

问题：递归解法的效率很低，因为存在大量重复计算。
优化：使用哈希表存储已经计算过的值，避免重复计算。

代码实现：

import java.util.*;

public class Main {
    static Map<Integer, Integer> map = new HashMap<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(ways(10));
    }
    static int ways(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(map.containsKey(n)) {
            return map.get(n);
        } else {
            map.put(n, ways(n-1) + ways(n-2));
            return map.get(n);
        }
    }
}

记忆化递归通过存储中间结果，避免了重复计算，显著提高了效率。

解法三：动态规划

思路：
动态规划的核心是状态转移方程dp[i] = dp[i-1] + dp[i-2]，其中dp[i]表示到达第i阶的走法数。
我们可以通过循环逐步计算，而不需要递归调用。

代码实现：

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(ways(10));
    }
    static int ways(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        int a = 1, b = 2, temp = 0;
        for(int i = 3; i <= n; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;
    }
}

动态规划通过迭代计算，避免了递归的栈溢出问题，时间复杂度为O(n)，空间复杂度为O(1)。

解法四：组合数学

思路：
假设小兔子跳了k次2阶台阶，那么剩下的台阶需要用1阶跳。总共有n - 2k阶需要用1阶跳，总跳的次数为n - k次。
组合数C(n - k, k)表示选择k次2阶跳的方式数。

代码实现：

public class Main {
    public static void main(String[] args) {
        int totalSteps = 10;
        int ways = 0;
        for (int k = 0; k <= totalSteps / 2; k++) {
            int n = totalSteps - k;
            ways += combination(n, k);
        }
        System.out.println("兔子跳上10级台阶的方法数为: " + ways);
    }
    public static int combination(int n, int k) {
        if (k > n || k < 0) return 0;
        if (k == 0 || k == n) return 1;
        k = Math.min(k, n - k);
        int result = 1;
        for (int i = 1; i <= k; i++) {
            result = result * (n - k + i) / i;
        }
        return result;
    }
} 

组合数方法通过数学公式直接计算，避免了递归和迭代，时间复杂度为O(n/2)。

Python实现

以下是Python版本的动态规划解法：

n = int(input())

def fbnq(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    a, b = 1, 2
    for i in range(3, n + 1):
        a, b = b, a + b
    return b

print(fbnq(n))

总结

1. 递归解法：简单直观，但效率低下。
2. 记忆化递归：通过存储中间结果优化了递归，但仍有递归深度限制。
3. 动态规划：时间复杂度和空间复杂度最优，适合大规模数据。
4. 组合数学：数学方法优雅，但需要理解组合数的计算逻辑。

延伸思考

1. 如果小兔子可以跳1阶、2阶或3阶，如何修改上述解法？
2. 如何将动态规划的时间复杂度进一步优化？

希望这篇文章能帮助大家更好地理解爬楼梯问题的多种解法！如果有任何问题，欢迎在评论区留言讨论~ 🐇