Dynamic programming

  class Program
    {

        static long[] numbersFib;

        static long Fib(int n)
        {
            if (numbersFib[n] == 0)
            {
                numbersFib[n] = Fib(n - 1) + Fib(n - 2);
            }

            return numbersFib[n];
        }

        static long[] numbersTrib;
        static long Tribonaci(int n)
        {
            if (numbersTrib[n] == 0)
            {
                numbersTrib[n] = Tribonaci(n - 3) + Tribonaci(n - 2) + Tribonaci(n - 1);
            }
            return numbersTrib[n];
        }

        static int[] dp;
        static int Solve(int n)
        {
            if (n < 0)
            {
                return 0;
            }
            if (n == 0)
            {
                return 1;
            }
            if (dp[n] == -1)
            {
                dp[n] = Solve(n - 1) + Solve(n - 3) + Solve(n - 5);
            }
            return dp[n];
        }
        static void Main(string[] args)
        {
            Console.Write("n = ");
            int n = int.Parse(Console.ReadLine());

            numbersFib = new long[n + 1];
            numbersFib[1] = 1;
            numbersFib[2] = 1;
            long fib = Fib(n);
            Console.WriteLine($"Fib({n}) = {fib}");

            numbersTrib = new long[n + 1];
            numbersTrib[1] = 1;
            numbersTrib[2] = 1;
            numbersTrib[3] = 2;
            long trib = Tribonaci(n);
            Console.WriteLine($"Trib({n}) = {trib}");

            dp = new int[n + 1];
            for (int i = 0; i < dp.Length; i++)
            {
                dp[i] = -1;
            }
            int count = Solve(n);
            Console.WriteLine($"1-3-5 sum count for {n}: {count}");
        }
    }