using System;

​

public class Program

{

    public static void Main()

    {

        int steps = findStepsByDp(7);

        Console.WriteLine("Hello World DP " + steps);

        steps = findSteps(7);

        Console.WriteLine("Hello World " + steps);

    }

​

    static int findSteps(int n)

    {

        if (n == 1)

            return 0;

        int ret = 1 + findSteps(n - 1);

        if (n % 2 == 0)

        {

            int temp = 1 + findSteps(n / 2);

            if (temp < ret)

            {

                ret = temp;

            }

        }

​

        if (n % 3 == 0)

        {

            int temp = 1 + findSteps(n / 3);

            if (temp < ret)

            {

                ret = temp;

            }

        }

​

        return ret;

    }

​

    static int findStepsByDp(int n)

    {

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

        dp[1] = 0;

        for (int i = 2; i <= n; i++)

        {

            dp[i] = 1 + dp[i - 1];

            if (i % 2 == 0)

            {

                dp[i] = getMin(dp[i], 1 + dp[i / 2]);

            }

​

            if (i % 3 == 0)

            {

                dp[i] = getMin(dp[i], 1 + dp[i / 3]);

            }

​

            Console.WriteLine("i = " + i + " steps " + dp[i]);

        }

​

        return dp[n];

    }

​

    static int getMin(int i, int j)

    {

        return i < j ? i : j;

    }

}