3级台阶问题 (记忆化搜索)

Question

3级台阶问题 (记忆化搜索)
题目描述

楼梯有 n (70 >= n > 0) 阶台阶，上楼时可以一步上 1 阶， 也可以一步上 2 阶，也可以一步上 3 阶，编程计算共有多少种不同的走法。

输入描述：

第一行为 t 组数据

接下来t行，每一行一个整数，即为台阶数 n。

输出描述：

共 t 行，每一行为相应台阶数下走法的数目。

输入样例：

5
1
2
3
4
5
输出样例：

1
2
4
7
13

Answer 1

#include<iostream>
long long a[75]={0};
long long f(int n){
    if (n <= 0) return 0; 
    if(n == 1)
        return 1;
    if(n == 2)
        return 2;
    if(n == 3)
        return 4;
    if (a[n] != 0) return a[n]; 
    return a[n]=f(n - 1) + f(n - 2) + f(n - 3);
}
 
int main(){
    int t;
    std::cin >> t;
    for (int j = 0; j <= 75; j++) {
        a[j] = 0;
    }
    for (int i = 0; i < t; i++) {
        int n;
        std::cin >> n;
            
        
        std::cout << f(n) << std::endl;
    }
    return 0;
}