PrimitiveCalculatorDP.java

import java.util.*;

public class PrimitiveCalculator 
{
    /* 
    * As usual for DP, three Steps are involved:
    * 1. Break down the main problem into sub problems.
    * 2. Initialize cache to hold solutions to sub problems.
    * 3. Build solution to main problem from sub problem.
    */
    private static List<Integer> optimal_sequence(int n) 
    {
        if (n == 1) 
        {
            return Arrays.asList(1);
        }

        List<Integer> sequence = new ArrayList<Integer>();

        //Minimum number of operations needed for 0 & 1 is 0.
        int[] memo = new int[n+1];
        memo[0] = 0;
        memo[1] = 0;

        // We need to calculate minimum number of operations needed for each number from 2 to n.
        for (int i = 2; i <= n; i++) 
        {
            // We need to check which of the following will give the minimum value.
            int multiplicationby2 = Integer.MAX_VALUE;
            int multiplicationby3 = Integer.MAX_VALUE;
            int additionby1 = Integer.MAX_VALUE;

            // Check if the number is divisible by 2.
            if (i % 2 == 0)
            {
                // get memo value at i/2
                multiplicationby2 = memo[i/2] + 1;
            }

            // Check if the number is divisible by 3. (adding + 1 to signify that we chose this current case).
            if (i % 3 == 0) 
            {
                // get memo value at i/3
                multiplicationby3 = memo[i/3] + 1;
            }

            // Check if the number when subtracted by 1 is greater than 0.
            if (i - 1 >= 0)
            {
                // get memo value at i-1
                additionby1 = memo[i-1] + 1;
            }

            memo[i] = Math.min(multiplicationby2, Math.min(multiplicationby3, additionby1));
        }

        // Recreate the sequence
        int i = n;
        while(i > 1) 
        {
            sequence.add(i);

            if (memo[i] == memo[i-1] + 1) 
            {
                i = i - 1;
            } 
            else if (i % 2 == 0 && memo[i] == memo[i/2] + 1) 
            {
                i = i/2;
            } 
            else if (i % 3 == 0 && memo[i] == memo[i/3] + 1) 
            {
                i = i/3;
            }
        }

        sequence.add(1);
        Collections.reverse(sequence);
        return sequence;
    }

    public static void main(String[] args) 
    {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> sequence = optimal_sequence(n);
        System.out.println(sequence.size() - 1);
        for (Integer x : sequence) 
        {
            System.out.print(x + " ");
        }
    }
}