70. 爬楼梯

class Solution {
  vector<int> DP{0, 1, 2};
public:
  int climbStairs(int n) {
    DP.reserve(n + 1);

    for (int i = 3; i <= n; ++i)
      DP[i] = DP[i - 1] + DP[i - 2];

    return DP[n];
  }
};

class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

class Solution {
public:
  int climbStairs(int n) {
    vector<int> PossibleWays(50);
    PossibleWays[0] = 1; // Already at the top.
    PossibleWays[1] = 1; // Only one way (+1) to the top.

    // Continue calculating the remaining possibilities. Keep in mind that the
    // analogy is thinking BACKWARDS instead of forwards.
    for (int i = 2; i <= n; ++i)
      // [i - 1] means +1 to n; [i - 2] means +2 to n.
      PossibleWays[i] = PossibleWays[i - 1] + PossibleWays[i - 2];

    return PossibleWays[n];
  }
};