暴力递归

#include <bits/stdc++.h>
using namespace std;
// 返回数列第 x 项
int f(int x)
{
    if (x == 1)
        return 1;
    if (x == 2)
        return 1;
    return (f(x - 1) + f(x - 2)) % 1000;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        cout << f(x) << "\n";
    }
    return 0;
}

记忆化递归

#include <bits/stdc++.h>
using namespace std;

// 【一】掏出小本子
// book[i] 记住 f(i)
int book[1000000 + 5];

// 返回数列第 x 项
int f(int x)
{
    // 【四】如果之前记过了，就别重新算了，直接返回
    if (book[x] != -1)
        return book[x]; 

    if (x == 1)
        return book[x] = 1; // 【三】先记下来再返回
    if (x == 2)
        return book[x] = 1; // 【三】先记下来再返回
    // 【三】先记下来再返回
    return book[x] = (f(x - 1) + f(x - 2)) % 1000;
}
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) << "\n";
    }
    return 0;
}