一、问题描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

二、方案一：递归

1、思路

递归方法遵循问题的直接描述。要到达第 n 阶，你可以从第 n-1 阶爬 1 阶，或者从第 n-2 阶爬 2 阶。因此，爬到第 n 阶的方法数等于爬到第 n-1 阶和第 n-2 阶的方法数之和。

2、代码实现

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    return climbStairs(n-1) + climbStairs(n-2)
}

3、复杂度分析

• 时间复杂度：O(2^n)，因为每个函数调用都会生成两个新的函数调用，形成一棵递归树。
• 空间复杂度：O(n)，因为递归树的深度可以达到 n。

三、方案二：动态规划

1、思路

动态规划方法通过存储已经计算过的爬楼梯方法数来避免重复计算。我们可以使用一个数组或哈希表来存储这些值。

2、代码实现

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    dp := make([]int, n+1)
    dp[1], dp[2] = 1, 2
    for i := 3; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

3、复杂度分析

• 时间复杂度：O(n)，因为每个数字只计算一次。
• 空间复杂度：O(n)，因为我们需要一个数组来存储 n+1 个爬楼梯方法数。

四、方案三：动态规划（空间优化）

1、思路

在动态规划的基础上，我们可以观察到，计算爬到第 n 阶的方法数只需要第 n-1 阶和第 n-2 阶的方法数。因此，我们不需要存储整个数组，只需要存储前两个阶的方法数。

2、代码实现

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    prev, curr := 1, 2
    for i := 3; i <= n; i++ {
        next := prev + curr
        prev, curr = curr, next
    }
    return curr
}

3、复杂度分析

• 时间复杂度：O(n)，因为每个数字只计算一次。
• 空间复杂度：O(1)，因为我们只需要常数级别的额外空间来存储前两个阶的方法数。

五、总结

递归方法虽然直观，但效率低下，特别是对于较大的 n。动态规划方法通过存储已经计算过的值来提高效率。进一步的空间优化可以将空间复杂度降低到常数级别。因此，对于这个问题，推荐使用动态规划的空间优化版本。