70. 爬楼梯

描述

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

示例

示例 1：
  输入： 2
  输出： 2
  解释： 有两种方法可以爬到楼顶。
    1.  1 步 + 1 步
    2.  2 步

示例 2：
  输入： 3
  输出： 3
  解释： 有三种方法可以爬到楼顶。
    1.  1 步 + 1 步 + 1 步
    2.  1 步 + 2 步
    3.  2 步 + 1 步

思路

1. 自底向上的动态规划，状态方程为f(n) = f(n-1) + f(n-2)，本质是一个斐波那契数列问题。

class Solution_70 {
 public:
  int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int m1 = 2, m2 = 1, m = 0;
    for (int i = 2; i < n; ++i) {
      m = m1 + m2;
      m2 = m1;
      m1 = m;
    }
    return m;
  }
};