27. 爬楼梯：一个人要爬n阶楼梯，每次可以爬1阶或2阶，计算有多少种不同的爬楼梯方法

爬楼梯问题是经典的动态规划问题。要计算有多少种不同的爬楼梯方法，假设你一共有 n 阶楼梯，每次可以选择爬 1 阶或者 2 阶。

一、问题分析

假设 f(n) 表示爬 n 阶楼梯的方法总数。对于 n 阶楼梯，有以下两种可能的情况：

1. 最后一步爬 1 阶：那么在这一步之前已经爬了 n-1 阶，此时总方法数为 f(n-1)。
2. 最后一步爬 2 阶：那么在这一步之前已经爬了 n-2 阶，此时总方法数为 f(n-2)。

因此，f(n) 可以表示为：

f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)f(n)=f(n−1)+f(n−2)

这是一个典型的斐波那契数列，边界条件为：

• 当 n = 1 时，f(1) = 1，即只有一种方法。
• 当 n = 2 时，f(2) = 2，即可以爬 1 阶 + 1 阶，或者直接爬 2 阶。

二、动态规划实现

动态规划的基本思想是将问题分解为子问题，通过保存中间结果来避免重复计算。

1. 代码实现

public class ClimbingStairs {

    public static int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        int n = 5;
        int result = climbStairs(n);
        System.out.println("Number of ways to climb " + n + " stairs: " + result);
    }
}

2. 时间复杂度和空间复杂度

• 时间复杂度：O(n)，因为我们只需要从 3 到 n 计算一遍，时间复杂度是线性的。
• 空间复杂度：O(n)，因为使用了一个数组来存储计算结果。

三、优化：空间优化的动态规划

我们注意到，在动态规划实现中，f(n) 只依赖于 f(n-1) 和 f(n-2)，所以我们可以用两个变量来替代数组，从而将空间复杂度优化到 O(1)。

1. 代码实现

public class ClimbingStairsOptimized {

    public static int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        int first = 1;
        int second = 2;
        int third = 0;

        for (int i = 3; i <= n; i++) {
            third = first + second;
            first = second;
            second = third;
        }

        return third;
    }

    public static void main(String[] args) {
        int n = 5;
        int result = climbStairs(n);
        System.out.println("Number of ways to climb " + n + " stairs: " + result);
    }
}

2. 时间复杂度和空间复杂度

• 时间复杂度：O(n)，和之前一样，依然是线性时间。
• 空间复杂度：O(1)，只用了常数个变量，空间复杂度是常数级的。

四、总结

爬楼梯问题可以通过动态规划解决，这是一个典型的递归问题，通过将问题分解为子问题并记录中间结果，避免了重复计算。在优化版本中，我们将空间复杂度从 O(n) 优化到了 O(1)，更为高效。

这种思路不仅适用于爬楼梯问题，还可以扩展到其他类似的递归或动态规划问题。