假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 编写程序，返回结果，同时写出程序的时间复杂度。

以下是Python程序，用于计算爬楼梯的不同方法数：

def climbStairs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

n = 5
print(climbStairs(n))

时间复杂度为O(n)，因为我们使用了一个循环来计算dp数组中的每个元素。

相关问题

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

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

答案是斐波那契数列。斐波那契数列是指：1、1、2、3、5、8、13、21、34、……，即第一项和第二项为1，从第三项开始，每一项都等于前两项之和。

因为每次只能爬1或2个台阶，所以爬到第n阶的方法数就等于爬到第n-1阶和爬到第n-2阶的方法数之和。而爬到第1阶和第2阶的方法数都是1，所以可以得到递推公式：

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

其中f(n)表示爬到第n阶的方法数。根据递推公式，可以用递归或循环的方式求解斐波那契数列，从而得到爬楼梯的方法数。

### 回答2：
这个问题属于经典的动态规划问题，我们可以用递推的方法来解决。

当 n=1 时，显然只有一种方法可以爬到楼顶，也就是一步一步爬。

当 n=2 时，有两种方法可以到达楼顶，一种是一次爬两步，另一种是先爬一步，再爬一步。

当 n>2 时，我们假设到达第 i 阶的方法有 f(i) 种。那么到达第 i 阶可以分为两种情况：

1. 在第 i-1 阶时向上爬一步。

2. 在第 i-2 阶时向上爬两步。

因此，f(i) = f(i-1) + f(i-2)。

最后只需要算出 f(n) 就可以知道到达楼顶的不同方法了。

我们可以用一个数组来存储 f(i)。初始时，f(1)=1，f(2)=2。

然后从 f(3) 开始，每个 f(i) 都等于前面两项的和，也就是 f(i-1) + f(i-2)。

最后返回 f(n) 就是到达楼顶的不同方法数了。

总结一下，假设你需要爬 n 阶楼梯才能到达楼顶，你有 f(n) 种不同的方法可以爬到楼顶。

其中，f(1)=1，f(2)=2，f(i)=f(i-1) + f(i-2) (i>=3)。

### 回答3：
我们可以用动态规划的思想来解决这个问题。设 f(i) 为到第 i 阶台阶时爬楼的方法数目，因为每一步都只能向上爬 1 阶或 2 阶台阶，所以到达第 i 阶台阶的方法只有两种：从第 i-1 阶向上爬 1 阶，或者从第 i-2 阶向上爬 2 阶。所以我们可以得到状态转移方程：

f(i) = f(i-1) + f(i-2)

同时，为了递推出 f(i) 的值，我们还需要初始化 f(1) 和 f(2) 的值。因为到第 1 阶台阶只有一种方法，我们有：f(1) = 1；到第 2 阶台阶有两种方法，我们有：f(2) = 2。所以最终的思路就是：从第 3 阶台阶开始递推，每次用上面的状态转移方程求出 f(i) 的值，直到求出 f(n) 的值为止。

以下是代码实现：

int climbStairs(int n) {
int f[n+1];
memset(f, 0, sizeof(f));
f[1] = 1;
f[2] = 2;
for (int i = 3; i <= n; i++) {
f[i] = f[i-1] + f[i-2];
}
return f[n];
}

算法的时间复杂度为 O(n)，空间复杂度为 O(n)，可以满足数据规模限制。因此，我们可以用这个算法来计算爬楼梯的方法数目。

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

可以使用递归或动态规划的方法来解决这个问题。假设n阶楼梯有f(n)种不同的爬法，那么可以得到以下递推式：

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

其中f(1) = 1，f(2) = 2。这个递推式的意思是，要到达第n阶楼梯，可以从第n-1阶楼梯爬1个台阶，或者从第n-2阶楼梯爬2个台阶。因此，到达第n阶楼梯的方法数就是到达第n-1阶楼梯的方法数加上到达第n-2阶楼梯的方法数。

使用递归的方法可以很容易地实现上述递推式，但是会存在重复计算的问题，因此可以使用动态规划的方法来优化。具体来说，可以使用一个数组dp来保存每一阶楼梯的方法数，然后从前往后依次计算即可。最终，dp[n]就是到达第n阶楼梯的方法数。