Я имею дело с проблемой, которая очень похожа на проблему смены монет.

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

Целью является положительное целое число n, найдите минимальное количество операций, необходимое для получения числа n, начиная с номера 1.

Я сделал жадный подход к этому, но это показывает неверные результаты

import sys

def optimal_sequence(n):
    sequence = []
    while n >= 1:
        sequence.append(n)
        if n % 3 == 0:
            n = n // 3
        elif n % 2 == 0:
            n = n // 2
        else:
            n = n - 1
    return reversed(sequence)

input = sys.stdin.read()
n = int(input)
sequence = list(optimal_sequence(n))
print(len(sequence) - 1)
for x in sequence:
    print(x)

Например:

Input: 10
Output: 
4
1 2 4 5 10

4 шага Но правильным является 3 шага:

Output: 
3
1 3 9 10

Я читал о динамическом программировании и надеюсь, что смогу реализовать его здесь. Но я не могу понять, как правильно его использовать в конкретном случае, может кто-нибудь дать мне совет?