Memoization Approach, C#

Language: Layout:

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            // Total Number of steps in stairs
            var totalNumberOfSteps = 4;
            // Total Number of allowed steps
            var numberOfStepsAllowed = 2;
            dynamic result = ClimbSteps(numberOfStepsAllowed, totalNumberOfSteps);
            Console.WriteLine(result.Mem);
            Console.WriteLine(string.Join(", ", result.Print));
            Console.ReadLine();
        }

private static dynamic ClimbSteps(int numberOfStepsAllowed, int totalNumberOfSteps)
        {
            var memList = Enumerable.Repeat(0, totalNumberOfSteps + 1).ToArray();
            var printList = new string[totalNumberOfSteps + 1][];
            if (numberOfStepsAllowed != 0)
            {
                memList[0] = 0;
                printList[0] = new[] { "" };
                memList[1] = 1;
                printList[1] = new[] { "1" };
                memList[2] = 2;
                printList[2] = numberOfStepsAllowed > 1 ? new[] { "1 1", "2" } : new[] { "1 1" };
                for (var indexTot = 3; indexTot <= totalNumberOfSteps; indexTot++)
                {
                    for (var indexSteps = 1; indexSteps <= numberOfStepsAllowed && indexTot - indexSteps > 0; indexSteps++)
                    {
                        var indexTotalStep = indexTot;
                        var indexAllowedStep = indexSteps;

memList[indexTot] += memList[indexTot - indexSteps];

var cartesianValues = (from x in printList[indexSteps] from y in printList[indexTotalStep - indexAllowedStep] select x + " " + y)
                            .Union(from x in printList[indexSteps] from y in printList[indexTotalStep - indexAllowedStep] select y + " " + x).Distinct();
                        printList[indexTot] = printList[indexTot] == null
                                           ? cartesianValues.ToArray()
                                           : printList[indexTot].Union(cartesianValues).Distinct().ToArray();
                    }
                }
            }
            return new { Mem = memList[totalNumberOfSteps], Print = printList[totalNumberOfSteps] };
        }
    }
}

Show compiler warnings [ + ] Show input
Compilation time: 0,17 sec, absolute running time: 10,01 sec, cpu time: 0,73 sec, average memory usage: 28 Mb, average nr of threads: 5