感觉这道题相比NC65 斐波那契数列，更适合拿来当作动态规划的入门训练题，因为相比 Fibonacci 数列已经给好了递推公式，这道题需要自己从实际问题中抽象出问题模型，虽然最终抽象出来还是 Fibonacci 数列哈。

下面是过程分析。

已知：

1. 爬到第 1 阶，只可能也只用爬 1 阶就能完成，共 1 种爬法
2. 爬到第 2 阶，可能是从先爬 1 阶到第 1 阶，然后再爬 1 阶到第 2 阶；也可能是直接爬 2 阶到第 2 阶，一共 2 种爬法
3. 爬到第 3 阶，可能直接来自于第 1 阶（一共 2 阶的距离），也可能来自于第 2 阶（一共 1 阶的距离），而如何爬到第 1 阶和第 2 阶？有多少种爬法？则回到了步骤 1 和 2
4. 归纳一下：在第 n 阶时，可能是由从第 n-2 阶爬 2 阶达到，也可能由从第 n-1 阶爬 1 阶达到（n>2）

用 记录 爬到第 n 阶时可能有多少种爬法，则：

暴力递归

int jumpFloor(int n) {
    if (n == 1 || n == 2)
        return n;
    return jumpFloor(n-2) + jumpFloor(n-1);
}

此方法存在 2 个问题：

1. 存在大量重复计算，比较耗时
2. 由于是递归，比较消耗栈空间

记忆递归

int helper(int* f, int n) {
    if (n == 1 || n == 2)
        f[n] = n;
    else if (f[n] == 0) // n>2 且 f[n] 未更新
        f[n] = helper(f, n-2) + helper(f, n-1);
    return f[n];
}

int jumpFloor(int n) {
    int f[n+1]; // f[n] 记录爬到第 n 阶有多少种方法
    memset(f, 0, sizeof(int)*(n+1)); // 此次值得注意，是以字节为单位去初始化的
    return helper(f, n);
}

还剩下一个问题：递归栈比较长

可以尝试转化为迭代

递推迭代

int jumpFloor(int n) {
    if (n == 1 || n == 2) 
        return n;
    int f[n+1]; // f[n] 记录爬到第 n 阶有多少种方法
    memset(f, 0, sizeof(int)*(n+1));
    f[1] = 1; f[2] = 2;
    for (int i = 3; i <= n; ++i) {
        f[i] = f[i-2] + f[i-1]; // 状态转移
    }
    return f[n];
}

本题要求的只是爬到第 n 阶有多少种爬法，所以不必保存爬到所有阶对应的爬法计数。

根据递推关系 ，可知，与第 n 项有直接关系的只有第 n-1 和 n-2 项，所以只需保存这 3 个位置

递推迭代+状态压缩

int jumpFloor(int n) {
    if (n == 1 || n == 2) 
        return n;
    int pre2 = 1, pre1 = 2, curr;
    for (int i = 3; i <= n; i++) {
        curr = pre2 + pre1;
        pre2 = pre1;
        pre1 = curr;
    }
    return curr;
}

还可以简化成只记录 2 个位置

递推迭代+状态压压缩

int jumpFloor(int n) {
    if (n == 1 || n == 2)
        return n;
    int pre = 1, cur = 2;
    for (int i = 3; i <= n; i++) {
        cur = pre + cur;
        pre = cur - pre;
    }
    return cur;
}