Задачка на динамическое программирование: листинг операций

Немножко усложним предыдущую задачку: потребуем, чтобы выводился список операций над числом, а не только их количество.

Заведем массив ops, который будет содержать в себе признаки операций для каждого числа. 1 - операция вычитания единицы, 2 - операция деления на два, 3 - операция деления на три.

Код:

public class Problem {
 
    static int[] ops;
 
    static int getMinSteps(int n) {
        if (n==1) return 0;
        else {
            int[] steps = new int[n+1];
            ops   = new int[n+1];
            steps[0] = -1;
            steps[1] = 0;
            ops[0] = ops[1] = -1;
            for (int i=2; i<=n; i++) {
                steps[i] = steps[i-1]+1;
                ops[i] = 1;
                if (i%2==0) {
                    int oldvalue = steps[i];
                    steps[i] = min(steps[i],steps[i/2]+1);
                    if (steps[i] != oldvalue) ops[i] = 2;
                } 
                if (i%3==0) {
                    int oldvalue = steps[i];
                    steps[i] = min(steps[i],steps[i/3]+1);
                    if (steps[i] != oldvalue) ops[i] = 3;
                }
            }
            return steps[n];
        }
    }
 
    static int min(int a, int b) {
        return a < b ? a : b;
    }    
 
    public static void main(String[] args) {
        if (args.length != 1) {
            System.err.println("Should be exectly one argument (natural number)!");
            return;
        }
        int n;
        try {
            n = Integer.parseInt(args[0]);
        } catch (NumberFormatException nfe) {
            System.err.println("Argument should be a natural number!");
            return;
        }
        if (n <= 0) {
            System.err.println("Wrong argument!");
            return;
        }
        System.out.println("Minimum number of steps: " + getMinSteps(n));
        printOps(n);        
    }
 
    static void printOps(int n) {
        System.out.println("Operations:");
        int i=n;
        while (i>1) {
            if (ops[i] == 1) {
                System.out.println("-1 ("+i+"-1="+(i-1)+")");
                i--;
            } else if (ops[i] == 2) {
                System.out.println("/2 ("+i+"/2="+(i/2)+")");
                i=i/2;
            } else if (ops[i] == 3) {
                System.out.println("/3 ("+i+"/3="+(i/3)+")");
                i=i/3;
            }
        }
    }
}

Пример вывода программы:

>java Problem 11212
Minimum number of steps: 15
Operations:
-1 (11212-1=11211)
/3 (11211/3=3737)
-1 (3737-1=3736)
-1 (3736-1=3735)
/3 (3735/3=1245)
/3 (1245/3=415)
-1 (415-1=414)
/3 (414/3=138)
/3 (138/3=46)
-1 (46-1=45)
/3 (45/3=15)
/3 (15/3=5)
-1 (5-1=4)
-1 (4-1=3)
/3 (3/3=1)