leetcode 链接：70. 爬楼梯

题目

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

示例：

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

解答 & 代码

解法一：动态规划（dp数组缓存）

设数组 dp，dp[i] 代表爬到 i 楼的方法数
状态转移方程：dp[i] = dp[i-2] + d[[i-1] （最后一次可以跳一阶 or 两阶，那么将跳 n -1 阶和跳 n-2 阶这两种方法数相加即可）
特殊情况（初始化）：dp[1] = 1, dp[2] = 2 

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2)
            return n;
        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; ++i)
            dp[i] = dp[i - 2] + dp[i - 1];
        return dp[n];
    }
};

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：6.1 MB, 在所有 C++ 提交中击败了 22.78% 的用户

解法二：动态规划（不用数组）

可以不需要数组，只需要记录跳 n-1 阶和跳 n-2 阶的方法数 dp2 和 dp1 

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2)
            return n;

        int dp1 = 1;
        int dp2 = 2;
        int dp;
        for(int i = 3; i <= n; ++i)
        {
            dp = dp1 + dp2;
            dp1 = dp2;
            dp2 = dp;
        }
        return dp;
    }
};

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了 80.50% 的用户