Пожалуйста помогите с задачей. Задача про Калькулятор с восстановлением ответа и именно восстановление ответа у меня не получается

Question

n = int(input())
F = [0] * (n + 1)
for i in range(2, n + 1):
    F[i] = F[i - 1]
    if i % 2 == 0:
        F[i] = min(F[i], F[i // 2])
    if i % 3 == 0:
        F[i] = min(F[i], F[i // 3])
    F[i] += 1
 print(F[n])

В моём коде выводится только наименьшее количество операций, но как сделать с восстановлением ответа я не знаю, пожалуйста подскажите. Вот сама задача:

Answer 1

Что происходит в строчках c min? Выбор того какое действие приводит к наилучшему результату для данного значения.

Вот и стоит вместо использования функции min делать своё сравнение, чтобы кроме выбора минимума, в параллельный список записывать номер ячейки, из которой пришли в данную (или F сделать списком списков из двух элементов, где второй будет содержать номер ячейки, из которой пришли в данную)

После прохода размотать назад наилучший путь, начиная с последнего элемента

Answer 2

В таблице F достатчно данных чтобы восстановить цепочку шагов. Для шага n отыскать предыдущий можно так:

если в ячейке n - 1 число на единицу меньше, то это нужный шаг
если n делится на 2 и в ячейке n // 2 число на единицу меньше, то это нужный шаг
если n делится на 3 и в ячейке n // 3 число на единицу меньше, то это нужный шаг
другого быть не может

Шаги отыскиваются задом наперёд. При печати их надо развернуть:

...

chain = []
while n > 1:
    chain.append(n)
    if F[n] == F[n - 1] + 1:
        n -= 1
    elif n % 2 == 0 and F[n] == F[n // 2] + 1:
        n //= 2
    elif n % 3 == 0 and F[n] == F[n // 3] + 1:
        n //= 3
    else:
        assert False
chain.append(1)
print(*chain[::-1])

БЛОГ НА HUSL

Пожалуйста помогите с задачей. Задача про Калькулятор с восстановлением ответа и именно восстановление ответа у меня не получается

Ответы (2 шт):