#include <bits/stdc++.h>
using namespace std;
int book[1000000+5]; //创建一个列表来存变量 
int f(int x)//递归算一下 
{
	if(book[x]!=-1)
		return book[x];
    if (x == 1)//因为题目要求，把0改成1 
        return 1;
    if (x == 2)
        return 1;
    book[x] = (f(x - 1) + f(x - 2))%1000;//这个是那个记忆化 
    return book[x];
}
int main()
{
	for(int i=1;i<=1000000;i++)//按照题目要求出另外几个输出数据 
		book[i] = -1; 
    int n;
    int T;
    cin>>T;
    for(int i=1;i<=T;i++){
	    cin >> n;
    	cout << f(n) % 1000 << "\n";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int book[1000000+5]; //记忆化，book[i] 记住斐波那契数列第i项 
//返回数列第 x 项
int f(int x)
{
	if(book[x]!=-1)
		return book[x];//之前算过就直接返回 
    if (x == 1)
        return 1;
    if (x == 2)
        return 1;
    book[x] = (f(x - 1) + f(x - 2))%1000;//算完后先别返回，先记下来 
    return book[x];
}
int main()
{
	//一开始把本子清空 
	for(int i=1;i<=1000000;i++)
		book[i] = -1; 
    int n;
    int T;
    cin>>T;
    for(int i=1;i<=T;i++){
	    cin >> n;
    	cout << f(n) % 1000 << "\n";
	}
	return 0;
}

代老师云：本题的记忆化搜索也可以使用递归做

感谢代老师对代码的认真指导、修改 ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️ ❤️

打表递推代码（基本的for循环）：

#include<bits/stdc++.h>
using namespace std;
int book[1000010]={0};
int n;
int main()
{
	for(int i=0;i<=1000005;i++)
		book[i]=-1;
//初始化；注意一定要为不可能的数字，如果初值为0的话会出问题的！（别问我怎么知道的）
	book[1]=1,book[2]=1;
//1、2两个数字均为1
	for(int i=3;i<=1000000;i++)
		if(book[i]==-1)
			book[i]=(book[i-1]+book[i-2])%1000;
//如果第i个数字不为-1，即没有使用过（其实不需要也可以不是吗），进行运算
//从1-1000000次循环确实有点暴力了
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		cout<<book[x]<<'\n';
//直接输出数组相应位数
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
//记忆化递归：book[i] 记住第 i 项的值
int book[1000005];
//返回数列第 x 项
int f(int x)
{
    //如果之前算过了，这次就不再计算了
    if (book[x] != -1)
        return book[x];
    if (x == 1)
        return 1;
    if (x == 2)
        return 1;
    //返回之前记录一下算出来的数
    book[x] = (f(x - 1) + f(x - 2)) % 1000;
    return book[x];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //把小本子上的东西清空
    //如果本子上记的是 -1 就说明之前没算过
    memset(book, -1, sizeof(book));
    int t, n;
    cin >> t;
    while (t--)
    {
        cin >> n;
        cout << f(n) << endl;
    }
    return 0;
}