if (n == 1 || n == 2) return n;
if (n == 3) return 4;

int *A = new int[n+1];
A[1] = 1;
A[2] = 2;
A[3] = 4;

for (int i = 4; i <= n; i++)
    A[i] = A[i - 1] + A[i - 2] + A[i - 3];

int ans = A[n];
delete[]A;

return ans;