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

Question

Я сейчас прохожу курс по алгоритмам.Я успешно выполнил это задание.Все тесты пройдены.Мой код выглядит грязным, и я хочу знать, есть ли в Python что-нибудь, что может помочь запустить мой код быстрее.Спасибо

Суть проблемы заключается в следующем: вам предоставляется примитивный калькулятор, который может выполнять следующие три операции с текущим числом ?: умножить ? на 2, умножить ? на 3 или добавить 1 к ?.Ваша цель - положительное целое число find, найдите минимальное количество операций, необходимое для получения числа ?, начиная с числа 1.

# Uses python3
import sys

def optimal_sequence(m):
    a=[0,0]
    for i in range(2,m+1):
        if i%3==0 and i%2==0:
            a.append(min(a[i//2],a[i//3],a[i-1])+1)
        elif i%3==0:
            a.append(min(a[i//3],a[i-1])+1)
        elif i%2==0:
            a.append(min(a[i//2],a[i-1])+1)
        else:
            a.append((a[i-1])+1)
    return backtrack(a,m)
def backtrack(a,m):
    result=[]
    result.append(m)
    current = m
    for i in range(a[-1],0,-1):
        if current%3==0 and a[current//3]==(i-1):
            current=current//3
            result.append(current)
        elif current%2==0 and a[current//2]==(i-1):
            current = current//2
            result.append(current)
        elif a[current-1]==(i-1):
            current = current-1
            result.append(current)
    return result

n = int(input())
if n == 1:
    print(0)
    print(1)
    sys.exit(0)

a= (optimal_sequence(n))
print(len(a)-1)
for x in reversed(a):
    print(x,end=" ")

Answer 1

Я бы использовал поиск в ширину для числа 1, начиная с числа n .Следите за номерами, которые были посещены, чтобы поиск возвращался по уже посещенным номерам.Для посещенных номеров запомните, с какого номера вы «пришли», чтобы достичь его, т.е. следующий номер по кратчайшему пути к n .

В моих тестах этот код работает быстрее, чем ваш:

from collections import deque

def findOperations(n):
    # Perform a BFS
    successor = {} # map number to next number in shortest path
    queue = deque() # queue with number pairs (curr, next)
    queue.append((n,None)) # start at n
    while True:
        curr, succ = queue.popleft()
        if not curr in successor: 
            successor[curr] = succ
            if curr == 1:
                break
            if curr%3 == 0: queue.append((curr//3, curr))
            if curr%2 == 0: queue.append((curr//2, curr))
            queue.append((curr-1, curr))
    # Create list from successor chain  
    result = []
    i = 1
    while i:
        result.append(i)
        i = successor[i]
    return result

Вызовите эту функцию с аргументом n :

findOperations(n)

Возвращает список.