using System;

using System.Collections.Generic;

​

public class Program

{       

    public static void Main()

    {

        int totalStairs = 23;

        int preciseLanding = 0;

        List<int> stepOptions = new List<int> { 1, 2, 3 };

​

        Climb(totalStairs, stepOptions, out preciseLanding);

        CountSteps(preciseLanding);

    }

​

    public static void Climb(int totalStairs, List<int> stepOptions, out int preciseLanding)

    {

        preciseLanding = 0;

        List<int> startingSteps = new List<int> { 0 };

​

        bool keepGoing = true;

        while (keepGoing)

        {

            List<int> thisBatch = new List<int>();

            foreach (int stepSize in stepOptions)

            {

                List<int> newSteps = new List<int>();

​

                foreach (int step in startingSteps)

                {

                    int totalSteps = step + stepSize;

​

                    if (totalSteps <= totalStairs)

                    {

                        newSteps.Add(totalSteps);

                    }

​

                    if (totalSteps == totalStairs)

                    {

                        preciseLanding++;

                    }

                }

​

                thisBatch.AddRange(newSteps);

            }

            startingSteps = new List<int>(thisBatch);

            keepGoing = startingSteps.Count > 0;

        }

    }

​

    public static void CountSteps(int preciseLandings)

    {

        Console.WriteLine("Number of paths that end exactly on 100 stairs: " + preciseLandings);

    }

}