using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Different ways of taking steps is: " + stepPerms(5));

    }

    /*

     * Complete the 'stepPerms' function below.

     *

     * The function is expected to return an INTEGER.

     * The function accepts INTEGER n as parameter.

     */

​

    //Recursive Programming takes O(3^N)

    /*public static int stepPerms(int n)

    {

        if(n < 0) return 0;

        if( n == 0 ) return 1;

        int[] steps= new int[]{1, 1, 2};

        return stepPerms(n-3)+stepPerms(n-2)+stepPerms(n-1);

    }*/

    //Memorization takes O(N)

    /*public static int stepPerms(int n)

    {

        return stepsPermsMemo(n, new int[n+1]);

    }

    public static int stepsPermsMemo(int n, int[] memo)

    {

        if(n < 0) return 0;

        if( n <= 1 ) return 1;

        memo[0] = 1;

        memo[1] = 1;

        memo[2] = 2;

        if(memo[n] == 0){

            memo[n] = stepsPermsMemo(n-3, memo) + stepsPermsMemo(n-2, memo) +

                        stepsPermsMemo(n-1, memo); 

        }

        return memo[n];

    }*/

​

    //Dynamic Programming

    /*public static int stepPerms(int n)

    {

        if(n < 0) return 0;

        if( n <= 1 ) return 1;

        int[] paths= new int[n + 1];

        paths[0] = 1;

        paths[1] = 1;

        paths[2] = 2;

        for(int i=3; i <= n; i++){

            paths[i] = paths[i-3] + paths[i-2] + paths[i-1]; 

        }

        return paths[n];

    }*/

    //Iterative

    public static int stepPerms(int n)

    {

        if(n < 0) return 0;

        if( n <= 1 ) return 1;

        //we keep only last three values in the array b'se the possibility of the steps          //count is 1, 2, 3

        int[] paths= {1, 1, 2};

        //we loop through the steps to get last three values and shift the last values 

        for(int i=3; i <= n; i++){

            int count = paths[2] + paths[1] + paths[0];

            //Shifting values to keep last three values only

            paths[0] = paths[1]; 

            paths[1] = paths[2];

            paths[2] = count;

        }

        //last value in the array holds the information

        return paths[2];

    }

​

}