#include <iostream>
using namespace std;

long long solve_1(int n)
{
    long long *res = new long long[n + 1];
    switch (n) {
    case 1: return 1;
    case 2: return 2;
    case 3: return 3;
    case 4: return 6;
    }
    res[1] = 1;
    res[2] = 2;
    res[3] = 3;
    res[4] = 6;
    for (int i = 5; i <= n; i++) {
        res[i] = res[i - 1] + res[i - 2] + res[i - 4];
    }
    long long x = res[n];
    delete [] res;
    return x;
}

long long solve_2(int n)
{
    switch (n) {
    case 1: return 1;
    case 2: return 2;
    case 3: return 3;
    case 4: return 6;
    }
    long long a = 1;
    long long b = 2;
    long long c = 3;
    long long d = 6;
    long long res;
    for (int i = 5; i <= n; i++) {
        res = d + c + a;
        a = b;
        b = c;
        c = d;
        d = res;
    }
    return d;
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        int x;
        cin >> x;
        cout << solve_2(x) << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;

long long solve(int n)
{
    long long *res = new long long[n + 1];
    switch (n) {
    case 1: return 1;
    case 2: return 2;
    case 3: return 3;
    case 4: return 6;
    }
    res[1] = 1;
    res[2] = 2;
    res[3] = 3;
    res[4] = 6;
    for (int i = 5; i <= n; i++) {
        res[i] = res[i - 1] + res[i - 2] + res[i - 4];
    }
    long long x = res[n];
    delete [] res;
    return x;
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        int x;
        cin >> x;
        cout << solve(x) << endl;
    }
    return 0;
}

--- 
+++ 
@@ -1,7 +1,7 @@
 #include <iostream>
 using namespace std;
 
-long long solve(int n)
+long long solve_1(int n)
 {
     long long *res = new long long[n + 1];
     switch (n) {
@@ -22,6 +22,29 @@
     return x;
 }
 
+long long solve_2(int n)
+{
+    switch (n) {
+    case 1: return 1;
+    case 2: return 2;
+    case 3: return 3;
+    case 4: return 6;
+    }
+    long long a = 1;
+    long long b = 2;
+    long long c = 3;
+    long long d = 6;
+    long long res;
+    for (int i = 5; i <= n; i++) {
+        res = d + c + a;
+        a = b;
+        b = c;
+        c = d;
+        d = res;
+    }
+    return d;
+}
+
 int main()
 {
     int T;
@@ -29,7 +52,7 @@
     while (T--) {
         int x;
         cin >> x;
-        cout << solve(x) << endl;
+        cout << solve_2(x) << endl;
     }
     return 0;
 }
Add a solution with better space cost to "Cached Calculations".
