Climbing Stairs
题目链接：
https://leetcode.cn/problems/climbing-stairs/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

Example 1:

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

Example 2:

1
2
3
4
5
6
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：
1 <= n <= 45

解题思路：

我们可以定义一个数组 dp 来记录爬到每个台阶的不同方法数，其中 dp[i] 表示爬到第 i 阶台阶的不同方法数。

由于每次只能爬 1 或 2 个台阶，所以我们可以得到如下的状态转移方程：

dp[i] = dp[i - 1] + dp[i - 2]

其中，dp[i - 1] 表示在前一个台阶只爬 1 个台阶的情况下到达当前台阶的方法数，dp[i - 2] 表示在前一个台阶爬 2 个台阶的情况下到达当前台阶的方法数。

边界条件是 dp[0] = 1 和 dp[1] = 1，因为爬到第 0 阶台阶只有一种方法，即不爬；爬到第 1 阶台阶也只有一种方法，即爬一步。

最终的答案就是 dp[n]，即爬到第 n 阶台阶的不同方法数。

源代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func climbStairs(_ n: Int) -> Int {
    if n == 0 || n == 1 {
        return 1
    }
    
    var dp = [Int](repeating: 0, count: n + 1)
    dp[0] = 1
    dp[1] = 1
    
    for i in 2...n {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    
    return dp[n]
}

该算法的时间复杂度为 O(n)，空间复杂度也为 O(n)。