Динамическое программирование для примитивного калькулятора

Question

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

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

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

я сделал жадный подход к что BUR он показывает неправильные результаты

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 

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

Answer 1

Просто решить с помощью простой рекурсии и Memoization:

Код:

d = {} 

def f(n): 
    if n == 1: 
     return 1, -1 
    if d.get(n) is not None: 
     return d[n] 
    ans = (f(n - 1)[0] + 1, n - 1) 

    if n % 2 == 0: 
     ret = f(n // 2) 
     if ans[0] > ret[0]: 
      ans = (ret[0] + 1, n // 2) 

    if n % 3 == 0: 
     ret = f(n // 3) 
     if ans[0] > ret[0]: 
      ans = (ret[0] + 1, n // 3) 

    d[n] = ans 
    return ans 

def print_solution(n): 
    if f(n)[1] != -1: 
     print_solution(f(n)[1]) 
    print n, 

def solve(n): 
    print f(n)[0] 
    print_solution(n) 
    print '' 

solve(10) 

Подсказка: F (X) возвращает кортеж (а, б), который a обозначает минимальные шаги, чтобы получить x от 1, а b обозначает предыдущее число, чтобы получить оптимальное решение. b используется только для печати решения.

Выход:

4 # solution for 10 
1 3 9 10 

7 # solution for 111 
1 2 4 12 36 37 111 

Вы можете отлаживать код и узнать, как это работает. Если вы новичок в DP, вы можете прочитать мой другой SO post о DP, чтобы быстро начать.

---

Поскольку Python не может рекурсию много (около 10000), я пишу итеративный вариант:

# only modified function print_solution(n) and solve(n) 

def print_solution(n): 
    ans = [] 
    while f(n)[1] != -1: 
     ans.append(n) 
     n = f(n)[1] 
    ans.append(1) 
    ans.reverse() 
    for x in ans: 
     print x, 

def solve(n): 
    for i in range(1, n): 
     f(i)[0] 
    print_solution(n) 
    print '' 

solve(96234) # 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234