[min step]

public class type {
    private static int[] memo;

    static int getMinSteps(int n) {
        if (n == 1)
            return 0;
        if (memo[n] != -1)
            return memo[n];
        int r = 1 + getMinSteps(n - 1);
        if (n % 2 == 0)
            r = Math.min(r, 1 + getMinSteps(n / 2));
        if (n % 3 == 0)
            r = Math.min(r, 1 + getMinSteps(n / 3));
        memo[n] = r;
        return r;
    }

    static int getMinStepsDP(int n) {
        int[] dp = new int[n + 1];
        int i;
        dp[1] = 0; // trivial case
        for (i = 2; i <= n; i++) {
            dp[i] = 1 + dp[i - 1];
            if (i % 2 == 0)
                dp[i] = Math.min(dp[i], 1 + dp[i / 2]);
            if (i % 3 == 0)
                dp[i] = Math.min(dp[i], 1 + dp[i / 3]);
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 7;
        memo = new int[n + 1];
        for (int i = 0; i < n + 1; i++)
            memo[i] = -1;
        System.out.println(getMinStepsDP(n));
    }
}