Programação dinâmica para calculadora primitiva

Estou lidando com o problema, que é bem parecido com o problema de trocar moedas.

Preciso implementar uma calculadora simples, que possa executar as três operações a seguir com o número atual x: multiplicar x por 2, multiplicar x por 3 ou adicionar 1 a x.

A meta recebe um número inteiro positivo n, encontre o número mínimo de operações necessárias para obter o número n começando pelo número 1.

Eu fiz uma abordagem gananciosa para isso, mas mostra resultados incorretos

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 exemplo:

Input: 10
Output: 
4
1 2 4 5 10

4 etapas. Mas o correto é três etapas:

Output: 
3
1 3 9 10

Eu li sobre programação dinâmica e espero poder implementá-la aqui. Mas, não consigo entender como usá-lo corretamente em um caso específico, alguém pode me dar um conselho?