题解 | #跳台阶#

常规迭代

// 重点思想是最后第n步有 n-1+1 n-2+2 这两种跳法
// 泛化即 fn = fn-1 + fn-2 ， 各分项再递归下去
class Solution {
  public:
    int jumpFloor(int number) {
      if (number <= 1) {
        return 1;
      }
      return jumpFloor(number - 1) + jumpFloor(number - 2);
    }
};

记忆节点

class Solution {
  public:
    int jumpFloor(int number) {
      if (number <= 1) {
        return 1;
      }
      if (step.count(number)) {
        return step[number];
      }
      return step[number] = jumpFloor(number - 1) + jumpFloor(number - 2);
    }
  private:
    std::map<int, int> step;     // 记录重复访问过的点
};

使用迭代（线性dp）

class Solution {
  public:
    int jumpFloor(int number) {
      int dp[number+1];    // 取到 number 步
      dp[0] = dp[1] = 1;
      for (int i = 2; i <= number; i++) {
        dp[i] = dp[i-1] + dp[i-2];        // 从底层逆推回去
      }
      return dp[number];
    }
};

压缩迭代

class Solution {
  public:
    int jumpFloor(int number) {
      int f_max, f_min;       // s1第一步 s2第二步
      f_max = f_min = 1;
      for (int i = 2; i <= number; i++) {
        int temp = f_max + f_min;
        f_min = f_max;
        f_max = temp;
      }
      return f_max;
    }
};