经分析，本题存在递推公式：dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

初始值：dp[1] = 1, dp[2] = 2, dp[3] = 4;

注意使用数据类型long long

可以通过剪枝来降低时间复杂度

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	int n;
	long long dp[5000];
	memset(dp, 0, sizeof(dp));
	dp[1] = 1, dp[2] = 2, dp[3] = 4;
	int index = 4;
	while (1) {
		cin >> n;
		if (n == 0)
			break;
		if (dp[n] == 0) {
			for (int i = index; i <= n; i++) {
				dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
			}
			index = n + 1;
		}
		cout << dp[n] << endl;
	}
	return 0;
}