Programación dinámica para calculadora primitiva.

Estoy lidiando con el problema, que es bastante similar al problema de cambio de monedas.

Necesito implementar una calculadora simple, que pueda realizar las siguientes tres operaciones con el número actual x: multiplicar x por 2, multiplicar x por 3 o sumar 1 a x.

El objetivo recibe un número entero positivo n, encuentre el número mínimo de operaciones necesarias para obtener el número n a partir del número 1.

Hice un enfoque codicioso para eso, pero muestra resultados incorrectos

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)

Por ejemplo:

Input: 10
Output: 
4
1 2 4 5 10

4 pasos Pero el correcto son 3 pasos:

Output: 
3
1 3 9 10

Leí sobre programación dinámica, y espero poder implementarla aquí. Pero, no puedo entender cómo usarlo correctamente en un caso particular, ¿alguien puede darme un consejo?