本文共 765 字，大约阅读时间需要 2 分钟。

要解决爬楼梯问题，我们需要计算有多少种不同的方法可以爬到顶部。每次只能爬1或2个台阶。这个问题可以通过动态规划来高效解决，避免了递归的重复计算和超时问题。

方法思想

我们知道，每一步的台阶数都可以分解为前一步加上1阶，或者前两步加上2阶。因此，f(n) = f(n-1) + f(n-2)，其中f(n)表示爬n阶的方法总数。

通过动态规划，我们逐步计算每一步的方法数，避免重复计算：

代码实现

public int climbStairs(int n) {    if (n == 0) return 0;    int[] ways = new int[n + 1];    ways[1] = 1;    if (n >= 2) {        ways[2] = 2;    }    for (int i = 3; i <= n; i++) {        ways[i] = ways[i - 1] + ways[i - 2];    }    return ways[n];}

讨论

这个方法使用动态规划的思想，维护一个数组ways，其中ways[i]表示爬i阶的方法总数。初始化时，设置基准情况（f(1)=1，f(2)=2），然后从f(3)开始逐步计算到f(n)。通过循环计算，每一步只依赖于前两步的结果，保证了算法的高效性。

• 时间复杂度：O(n)，线性时间，计算了每个台阶的方法数。
• 空间复杂度：O(n)，额外空间用于存储方法数数组。

这种方法适合处理较大的n值，能够在合理时间内给出答案。

转载地址：http://qegyk.baihongyu.com/