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?