Ich beschäftige mich mit dem Problem, das ist ziemlich ähnlich, Münzen Problem zu ändern.

Ich muss einen einfachen Taschenrechner implementieren, der die folgenden drei Operationen mit der aktuellen Zahl x ausführen kann: x mit 2 multiplizieren, x mit 3 multiplizieren oder 1 zu x addieren.

Goal erhält eine positive ganze Zahl n. Ermitteln Sie die minimale Anzahl von Operationen, die erforderlich sind, um die Zahl n zu erhalten, beginnend mit der Zahl 1.

Ich habe eine gierige Annäherung an das gemacht, aber es zeigt falsche Ergebnisse

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)

Beispielsweise

Input: 10
Output: 
4
1 2 4 5 10

4 Schritte. Aber die richtige ist 3 Schritte:

Output: 
3
1 3 9 10

Ich habe über dynamische Programmierung gelesen und hoffe, dass ich sie hier implementieren konnte. Aber ich kann im Einzelfall nicht richtig damit umgehen. Kann mir jemand einen Rat geben?