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

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

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

输入描述：

第一行为 t 组数据

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

输出描述：

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

输入样例：

5
1
2
3
4
5
输出样例：

1
2
4
7
13

用递归

// 洛谷 P1192 简化就是这题答案 
#include<bits/stdc++.h>
using namespace std;
int n,p[100005];
int dp(int x) {
    int ans=0;
    for(int i=1;i<=min(x,3);i++){
        if(!p[x-i]){
            ans+=p[x-i];
        }else{
            ans+=dp(x-i);
        }
    }
    p[x]=ans;
    return ans;
}
int main(){
    int n;
    cin>>n;
    cout<<dp(n);
    return 0;
}

简单递归，可以添加备忘录的方式或者转换成dp（动态规划）来优化时间复杂度。

#include<iostream>

int f(int n){
    if(n == 1)
        return 1;
    if(n == 2)
        return 2;
    if(n == 3)
        return 4;
    else
        return f(n - 1) + f(n - 2) + f(n - 3);
}

int main(){
    int len;
    std::cin>>len;
    for(int i = 0;i < len;i++){
    int n;
    std::cin>>n;
    std::cout<<f(n)<<std::endl;
    }
    return 0;
}