记忆化递归

#include <bits/stdc++.h>
using namespace std;
long long book[75];
long long f(int x)
{
    if (book[x] != -1)
        return book[x];
    if (x == 0)
        return book[x] = 1;
    if (x == 1)
        return book[x] = f(x - 1);
    if (x == 2)
        return book[x] = f(x - 1) + f(x - 2);
    return book[x] = f(x - 1) + f(x - 2) + f(x - 3);
}
int main()
{
    memset(book, -1, sizeof(book));
    int x;
    while (cin >> x)
    {
        if (x == 0)
            break;
        cout << f(x) << "\n";
    }
    return 0;
}

递推

#include <bits/stdc++.h>
using namespace std;
long long f[75];
int main()
{
    f[0] = 1;
    f[1] = 1;
    f[2] = 2;
    for (int i = 3; i <= 70; i++)
        f[i] = f[i - 1] + f[i - 2] + f[i - 3];
    int x;
    while (cin >> x)
    {
        if (x == 0)
            break;
        cout << f[x] << "\n";
    }
    return 0;
}