Найдите минимальные шаги, необходимые для достижения n

Question

Я пытаюсь решить задачу программирования Dynami c, которая выглядит следующим образом, но не могу ее решить.

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

Я нашел решение на самом stackoverflow , но не смог чтобы понять, что происходит.

Я слышал, что каждую проблему DP можно решить, создав матрицу, которую я пытался сделать, но не знаю, где я ошибаюсь. Ниже создана таблица, которая показывает количество шагов, необходимых для достижения n от 1, изначально я принимаю значения как бесконечность.

i / j           0           1             2            3                4              5
plus 1          0           1             2            3                4              5
multiple by 2   0           infinity      2            infinity         3             infinity
multiple by 3   0           infinity      infinity     2                infinity      infinity

Я пытаюсь решить эту проблему в Python. Кто-нибудь может мне помочь.

Я нашел решение, которое выглядит следующим образом, но не могу точно понять, что происходит:

import math
target = int(input())

def optVal(target, cache):
    result = [1] * cache[-1]  # 1
    for i in range(1, cache[-1]): # 2
        result[-i] = target  # 3
        if cache[target-1] == cache[target] - 1:  # 4
            target -= 1
        elif target % 2 == 0 and (cache[target // 2] == cache[target] - 1):  # 5
            target //= 2
        else:  # 6 # target % 3 == 0 and (cache[target // 3] == cache[target] - 1):
            target //= 3
    return result

cache = [0] + [math.inf] * target  # 1
for i in range(1, len(cache)):  # 2
    temp1 = math.inf
    temp2 = math.inf
    temp3 = math.inf

    temp1 = cache[i - 1] + 1
    if i % 2 == 0:
        temp2 = cache[i // 2] + 1
    if i % 3 == 0:
        temp3 = cache[i // 3] + 1

    cache[i] = min(temp1, temp2, temp3)

print('Minimum operation: ', cache[target] - 1)
finalLst = optVal(target, cache)
print(' '.join([str(x) for x in finalLst]))

Input: 
5
Output:
3
1245

Answer 1

Этот алгоритм разделен на две части. Первый - в основном, второй - в функции optVal.

Первая часть строит список cache, где cache[i] содержит минимальное количество шагов, необходимых для получения от 0 на i, применяя на каждом шаге одну из трех возможных операций: +1, *2 или *3. Этот список является одномерным случаем матрицы, о которой вы читаете.

Когда вычисляется cache[i], все индексы ниже i уже вычислены. Можно добраться до i тремя возможными способами, поэтому необходимо изучить максимум три возможных источника i, т. Е. Элементов cache: i-1, i//2 и i//3, но i//2 только если i четное, а i//3 только если i может быть разделено на 3. Эти элементы cache сравниваются, и содержимое победителя увеличивается на 1 (из-за дополнительного шаг для перехода к i), сохраняется в cache. Этот процесс запускается путем помещения 0 в cache[0]. В конце концов, cache[target] будет содержать минимальное количество шагов, чтобы добраться до target, начиная с 0 (что на 1 больше, чем количество шагов, чтобы добраться туда, начиная с 1, как была сформулирована проблема - обратите внимание, что вы можете применить только операцию +1 для выхода из 0).

Теперь, если бы я написал код, я бы, вероятно, сохранил «родительскую» или «выигрышную операцию» каждого cache[i] вместе с количеством шагов, чтобы добраться туда (кстати, эти math.inf на самом деле не нужны, потому что всегда есть конечное количество шагов для достижения i из-за операции +1.) Подход автора состоит в том, чтобы вывести эту информацию из содержания возможных родителей (максимум 3) каждого cache[i], которое необходимо исследовать. В обоих случаях цепочка «предков» должна быть реконструирована в обратном порядке, начиная с cache[target], и это то, что происходит в optVal().

В optVal() target изменяется на каждом итерация (немного сбивает с толку), потому что на каждой итерации у вас есть информация о минимальном количестве шагов, необходимых для достижения определенного целевого числа. Зная это, вы смотрите на 1, 2 или 3 возможных родителя, чтобы проверить, какой из них содержит именно такое количество шагов минус 1. Тот, который прошел тест, является фактическим родителем, и поэтому вы можете продолжить построение цепочки в обратном порядке, заменяя target с родителем.

Answer 2

, чтобы решить эту DP, вы должны построить таблицу с минимальным количеством шагов, необходимых для получения n, если были доступны одна, две или все операции. вы будете создавать его слева направо, сверху вниз, ie 1 до n, добавьте 1 к mul 3. По мере того, как вы go вниз, становится доступно больше операций

Значение ячеек зависит только от значение над ним (если доступно) и atmax 3 значения в левой части, например. для (n = 6), (mul 3) ячейка будет зависеть только от (n = 6),(mul 2) и (n = 2)(mul 3), (n = 3)(mul 3), (n = 5)(mul 3). затем вы сравните эти значения, и в зависимости от того, какое из них меньше после операции, вы поместите это значение, поэтому вы будете сравнивать значение (n = 2)(mul 3) + 1 vs (n = 3)(mul 3) + 1 vs (n = 5)(mul 3) + 1 vs (n = 6)(mul 2), а затем то, что меньше, вы поместите это значение

, поскольку задано n = 1, в первом столбце все значения будут равны нулю

для n = 2, его значения будут зависеть от значений n = 1. вы можете " добавить 1 "или" умножить на 2 "(1 шаг), оба значения действительны. поэтому этот столбец будет иметь все значения как 0 + 1 = 1

для n = 3, его значения будут зависеть от значений n = 1 (потому что 1 = 1/3 из 3) И n = 2. если вы можете «добавить 1» или «умножить на 2», тогда вы выберете прибавление 1 к n = 2, так что общее количество шагов 1 + 1 = 2. НО если вы также можете умножить на три, вам понадобится только один шаг, поэтому 0 + 1 = 1. поскольку 1 <2, вы установите 1 как это значение. поэтому записи для n = 3 равны 2, 2, 1 </p>

для n = 4, это будет зависеть от n = 3 (добавить 1) и n = 2 (mul 2). поэтому значения будут 3, 2, 2

для n = 5, это будет зависеть от n = 4 (добавить 1). поэтому значения будут 4, 3, 3

, поэтому минимальные шаги 3 для достижения n = 5

итоговая таблица:

    1  2  3  4  5
add 1  0  1  2  3  4
mul 2  0  1  2  2  3
mul 3  0  1  1  2  3