70. 爬楼梯

题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 45

---

解题分析及思路：

设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。

1. 当为 1 级台阶： 剩 n−1 个台阶，此情况共有 f(n−1) 种跳法。
2. 当为 2 级台阶： 剩 n−2 个台阶，此情况共有 f(n−2) 种跳法。

即 f(n) 为以上两种情况之和，即 f(n)=f(n−1)+f(n−2) ，以上递推性质为斐波那契数列。因此，本题可转化为 求斐波那契数列的第 n 项，区别仅在于初始值不同：

• 青蛙跳台阶问题： f(0)=1 , f(1)=1 , f(2)=2 。
• 斐波那契数列问题： f(0)=0 , f(1)=1 , f(2)=1 。

那么对应动态规划解法：

1. 定义状态： 设 dp[i] 表示爬到第 i 阶楼梯的不同方法数。

2. 找到状态转移方程： 对于第 i 阶楼梯，可以从第 i-1 阶楼梯爬一步上来，也可以从第 i-2 阶楼梯爬两步上来。因此，状态转移方程为：dp[i] = dp[i-1] + dp[i-2]。

3. 初始化： 初始化前两个状态，即 dp[0] = 1 和 dp[1] = 1，因为爬到第0阶和第1阶楼梯的方法数都是1。

4. 递推求解： 使用状态转移方程递推求解，计算出 dp 数组中的每个状态。

5. 计算最终结果： 最终结果是 dp[n]，即爬到第 n 阶楼梯的不同方法数。

func climbStairs(n int) int {
    if n == 0 || n == 1 {
        return 1
    }

    // 初始化前两个状态
    res := make([]int, n+1)
    res[0], res[1] = 1, 1

    // 递推求解
    for i := 2; i <= n; i++ {
        res[i] = res[i-1] + res[i-2]
    }

    // 返回最终结果
    return res[n]
}

状态压缩：

若新建长度为 n+1 的 res 数组，则空间复杂度为 O(N) 。

由于res数组第 i 项只与第 i−1 和第 i−2 项有关，因此只需要初始化长度 3。由于省去了 res数组没必要的空间，因此空间复杂度降至 O(1) 。

所以最终的解法：

1. 定义状态： 设 res 数组表示状态，其中 res[0] 表示爬到第 i-2 阶楼梯的方法数，res[1] 表示爬到第 i-1 阶楼梯的方法数，res[2] 表示爬到第 i 阶楼梯的方法数。
2. 找到状态转移方程： 对于第 i 阶楼梯，可以从第 i-1 阶楼梯爬一步上来，也可以从第 i-2 阶楼梯爬两步上来。因此，状态转移方程为：res[2] = res[0] + res[1]。
3. 初始化： 初始化前两个状态，即 res[0] = 0 和 res[1] = 0，因为爬到第 0 阶和第 1 阶楼梯的方法数都是 1。
4. 递推求解： 使用状态转移方程递推求解，通过不断更新 res 数组中的元素，计算出每一阶楼梯的不同方法数。
5. 计算最终结果： 最终结果是 res[2]，即爬到第 n 阶楼梯的不同方法数。

func climbStairs(n int) int {
    // res数组用来保存动态规划的状态
    // res[0]表示爬到第i-2阶楼梯的方法数
    // res[1]表示爬到第i-1阶楼梯的方法数
    // res[2]表示爬到第i阶楼梯的方法数
    res := []int{0, 0, 1}

    // 从第1阶楼梯开始，迭代计算每一阶的爬法
    for i := 0; i < n; i++ {
        res[0] = res[1]  // 更新爬到第i-2阶楼梯的方法数
        res[1] = res[2]  // 更新爬到第i-1阶楼梯的方法数
        res[2] = res[0] + res[1]  // 计算爬到第i阶楼梯的方法数
    }

    return res[2]  // 返回爬到第n阶楼梯的方法数
}

复杂度：

• 时间复杂度：复杂度为 O(N)，其中 N 为 n 的值。
• 空间复杂度：O(1)，只使用了有限的额外空间。

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:1.8 MB,击败了85.78% 的Go用户