当前位置： 面试刷题>> 爬楼梯(经典算法150题)
**题目描述补充**：
假设你正在爬楼梯。需要 n 步你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
**解题思路**：
这个问题可以使用动态规划（Dynamic Programming）的方法来解决。我们可以定义一个数组 `dp`，其中 `dp[i]` 表示到达第 `i` 阶楼梯的方法数。根据题目描述，我们知道到达第 `i` 阶楼梯可以由以下两种方式之一得到：
1. 从第 `i-1` 阶楼梯爬 1 步上来。
2. 从第 `i-2` 阶楼梯爬 2 步上来（如果 `i-2` 是非负的）。
因此，我们可以得到状态转移方程：
```
dp[i] = dp[i-1] + dp[i-2] (当 i > 2)
```
同时，初始条件为：
```
dp[1] = 1 # 只有一种方法到达第1阶楼梯，就是直接爬1步
dp[2] = 2 # 有两种方法到达第2阶楼梯，一种是直接爬2步，另一种是分两次爬1步
```
**PHP代码示例**：
```php
function climbStairs($n) {
if ($n <= 1) {
return $n;
}
$dp = array_fill(1, $n + 1, 0);
$dp[1] = 1;
$dp[2] = 2;
for ($i = 3; $i <= $n; $i++) {
$dp[$i] = $dp[$i - 1] + $dp[$i - 2];
}
return $dp[$n];
}
// 示例用法
echo climbStairs(5); // 输出: 8
```
**Python代码示例**：
```python
def climbStairs(n):
if n <= 1:
return n
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]
# 示例用法
print(climbStairs(5)) # 输出: 8
```
**JavaScript代码示例**：
```javascript
function climbStairs(n) {
if (n <= 1) {
return n;
}
let dp = new Array(n + 1).fill(0);
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// 示例用法
console.log(climbStairs(5)); // 输出: 8
```
以上代码示例分别用PHP、Python和JavaScript实现了爬楼梯问题的解决方案，并通过动态规划的方法求解了到达楼顶的不同方法数。这些代码片段可以直接在相应的环境中运行并验证结果。