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

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

Заведем массив 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)

Задачка на динамическое программирование: Minimum steps to one

Формулировка задачи на английском:

On a positive integer, you can perform any one of the following 3 steps. 
1.) Subtract 1 from it. ( n = n - 1 )  , 
2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2  )  , 
3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3  ). 

Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1
eg: 
1.)For n = 1 , output: 0       
2.) For n = 4 , output: 2  ( 4  /2 = 2  /2 = 1 )    
3.)  For n = 7 , output: 3  (  7  -1 = 6   /3 = 2   /2 = 1 )

Теперь формулировка на русском языке (в моем переводе):

Дано натуральное число n (не равное нулю). Над ним можно совершить одну из трех операций:
1) вычесть единицу из него (n-1)
2) разделить на два (n/2)
3) разделить на три (n/3)

Для данного числа n найти минимальное число операций, в результате которых получается единица. 
Пример: 
1) n=1, ответ: 0
2) n=4, ответ: 2 (/2, /2)
3) n=7, ответ: 3 (-1, /3, /2)

Рассмотрим решение.

Для каждого данного n непонятно, какая из операций приведет к минимальному числу шагов. Поэтому нужно попробовать все варианты и выбрать из них вариант с минимальным числом шагов.
Если n == 1, то F(n) = 0.
Иначе (если n>1):
F(n) = 1 + min(F(n-1),F(n/2),F(n/3)).
При этом каждый раз нужно проверять, делится ли n без остатка на два или на три.

Решение в коде на Java:

public class Problem {
 
    static int getMinSteps(int n) {
        if (n==1) return 0;
        else if (n==2 || n==3) return 1;
        else if (n==4) return 2;
        else {
            int[] steps = new int[n+1];
            steps[0] = -1;
            steps[1] = 0;
            steps[2] = steps[3] = 1;
            steps[4] = 2;
            for (int i=5; i<=n; i++) {
                steps[i] = steps[i-1]+1;
                if (i%2==0) {
                    steps[i] = min(steps[i],steps[i/2]+1);
                } 
                if (i%3==0) {
                    steps[i] = min(steps[i],steps[i/3]+1);
                }
            }
            return steps[n];
        }
    }
 
    static int min(int a, int b) {
        return a < b ? a : b;
    }    
 
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        System.out.println(getMinSteps(n));
    }
}

Задачка простенькая, но как вводный пример в динамическое программирование сгодится.
В коде нет, конечно, проверки на допустимые значения n (не проверяется, чтобы n было больше нуля), также нет проверки на отсутствие аргумента в командной строке. Главное здесь - познакомиться с подходом, который предлагает динамическое программирование для решения такого рода задач.