信息学奥赛一本通题目解析：1204：爬楼梯（记忆化递归）

【题目描述】

树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数。

例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级，也可以第一次走两级，第二次走一级，一共3种方法。

【输入】

输入包含若干行，每行包含一个正整数N，代表楼梯级数，1≤N≤30。

【输出】

不同的走法数，每一行输入对应一行输出。

【输入样例】

5
8
10

【输出样例】

8
34
89

【解题思路】

记忆化递归（也称作自顶向下的动态规划）通过存储已经计算过的结果来避免重复计算，这样可以显著提高递归解法的效率。在解决树老师爬楼梯问题时，可以用一个数组来保存每一级楼梯对应的走法数，当计算到某一级楼梯的走法时，首先检查这个结果是否已经被计算并存储过了，如果是的话直接返回该结果，否则进行计算，并将计算结果保存供后续使用。

记忆化递归解法思路：

1. 初始化一个数组用于存储计算过的走法数，数组的大小至少能容纳输入中的最大楼梯数N。由于题目给出的N最大值为30，我们可以安全地初始化一个大小为31的数组（从1开始索引）。

2. 编写递归函数，该函数接受两个参数：楼梯数n和一个用于存储计算结果的数组memo。函数首先检查memo[n]是否已经有值（非0），如果有，直接返回该值。否则，计算该楼梯数的走法数，并更新memo[n]。

3. 处理基本情况：如果n为1或2，走法数是已知的（分别为1和2），直接返回相应的值并更新memo数组。

4. 递归计算并返回结果。

【实现代码】

#include <iostream>
using namespace std;

int memo[31] = {0}; // 全局变量数组，用于记忆化递归存储走法数

// 记忆化递归函数，缩写为cs
int cs(int n) {
    if (memo[n] > 0) {
        // 如果已经计算过这个值，直接返回
        return memo[n];
    }
    if (n == 1) {
        memo[n] = 1; // 基本情况
    } else if (n == 2) {
        memo[n] = 2; // 基本情况
    } else {
        // 递归计算
        memo[n] = cs(n - 1) + cs(n - 2); // 移除不必要的模运算
    }
    return memo[n];
}

int main() {
    int N;
    while (cin>>N) {
        cout << cs(N) << endl; // 使用记忆化递归计算并输出结果
    }
    return 0;
}