LeetCode | 爬楼梯

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

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

public class Solution {
    #region 方法2: 循环
    public int ClimbStairs(int n)
    {
        if (n <= 1)
        {
            return 1;
        }
        // 注意: 长度: n + 1
        int[] arr = new int[n + 1];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < arr.Length; i++)
        {
            // arr[2] = arr[1] + arr[0]
            // arr[3] = arr[2] + arr[1]
            // arr[4] = arr[3] + arr[2]
            // ...
            // 在循环内最后一次: 再i++, 就会达到 Length, 从而不满足循环条件而退出
            // arr[n] = arr[n - 1] + arr[n -2]
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n];
    }
    #endregion
}

public class Solution {
    #region 方法3: 循环 压缩优化
    /// <summary>
    /// dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，没有必要存储所有计算过的 dp 项。用两个临时变量去存这两个状态就好
    /// </summary>
    /// <param name="n"></param>
    /// <returns></returns>
    public int ClimbStairs(int n)
    {
        int prev = 1, cur = 1;
        int temp;
        for (int i = 2; i < n + 1; i++)
        {
            temp = cur; // 暂存上一次的 cur
            cur = prev + cur; // 当前的 cur = 上上次cur + 上一次cur
            prev = temp; // prev 更新为 上一次 cur
        }

        return cur;
    }
    #endregion
}