Программное решение Dynami c для решения проблемы печати двумя пальцами на минимальном расстоянии

Question

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

У вас есть раскладка клавиатуры, как показано выше в плоскости XY, где каждая заглавная буква Engli sh расположена в некоторой координате, например, буква A расположена в координате (0,0 ), буква B расположена в точке с координатами (0,1), буква P расположена в точке с координатами (2,3), а буква Z расположена в точке с координатой (4,1).

Учитывая строковое слово, вернуть минимальное общее расстояние для ввода такой строки, используя только два пальца. Расстояние между координатами (x1, y1) и (x2, y2) равно | x1 - x2 | + | y1 - y2 |.

Обратите внимание, что начальные положения ваших двух пальцев считаются свободными, поэтому не учитывайте общее расстояние, также ваши два пальца не должны начинаться с первой буквы или первых двух букв.

Например, для входного слова "HAPPY" у нас будет:

Output: 6
Explanation: 
Using two fingers, one optimal way to type "HAPPY" is:
Finger 1 on letter 'H' -> cost = 0
Finger 1 on letter 'A' -> cost = Distance from letter 'H' to letter 'A' = 2
Finger 2 on letter 'P' -> cost = 0
Finger 2 on letter 'P' -> cost = Distance from letter 'P' to letter 'P' = 0
Finger 1 on letter 'Y' -> cost = Distance from letter 'A' to letter 'Y' = 4
Total distance = 6

Из того, что я читаю онлайн, есть 1D, 2D и 3D (с точки зрения пространства) динамические c программирование решения вышеуказанной проблемы. Я нашел 1D и 2D решения онлайн для решения этой проблемы, но я считаю, что им слишком сложно следовать, поэтому я надеюсь начать с 3D и постепенно понять более эффективные.

Что такое 3D DP-постановка этой проблемы? У этой проблемы есть имя в частности?

Я понимаю рекурсивную природу проблемы, но я пытаюсь сформулировать простое восходящее решение (например, в 3D).

Answer 1

Довольно простой подход к трехмерному динамическому c программированию заключается в следующем:

def dist(a,b): # gets distance between chars a and b
    y1,x1 = a/6,a%6
    y2,x2 = b/6,b%6
    return abs(y1-y2)+abs(x1-x2)

def solve(s):
    N = len(s)
    dp = [[[float('inf') for x in range(26)] for x in range(26)] for x in range(N+1)]
    dp[0] = [[0 for x in range(26)] for x in range(26)]
    for i in range(N):
         cur = ord(s[i])-ord('A')
         for j in range(26):
              for k in range(26):
                   dp[i+1][j][cur] = min(dp[i+1][j][cur], dp[i][j][k] + dist(k,cur)) # move right finger
                   dp[i+1][cur][k] = min(dp[i+1][cur][k], dp[i][j][k] + dist(j,cur)) # move left finger
    res = float('inf')
    for i in dp[N]:
         res = min(res,min(i))
    return res

В функции solve мы объявляем динамическую c таблицу программирования dp[N+1][26][26], и давайте хранить в ячейке dp[i][j][k] минимальное расстояние, необходимое для ввода всех символов в строке до, но не включая i-го символа, с левым пальцем на j-й клавише и правым пальцем на k-тая клавиша.

Наш базовый случай - i = 0, мы знаем, что требуется 0 общее расстояние, чтобы наши пальцы начинали где угодно, поэтому первый ряд полностью инициализируется с помощью 0 s. Затем происходит переход от всех возможных конфигураций двух пальцев к перемещению левого или правого пальца на новую клавишу. Если вы находитесь в состоянии dp[i][j][k], то после нажатия i-й клавиши (назовем ее cur), если мы нажимаем эту новую клавишу левым пальцем, обновленное состояние будет dp[i+1][cur][k], поскольку левый палец перешел с j на cur. Точно так же, если мы нажмем его правым пальцем, обновленное состояние будет dp[i+1][j][cur].

Наш окончательный ответ находится где-то в строке N+1, где N - длина строки , Мы просто берем минимум всех комбинаций левого и правого пальцев в этом ряду.

РЕДАКТИРОВАТЬ: Вот двумерное решение, которое я описал в комментариях:

def solve(s):
    N = len(s)
    dp = [[float('inf') for x in range(26)]for x in range(N)]
    dp[0] = [0 for x in range(26)]
    for i in range(1,N):
        cur = ord(s[i])-ord('A')
        lst = ord(s[i-1])-ord('A')
        for j in range(26): # one finger currently on s[i-1], other finger on j
             dp[i][j] = min(dp[i][j], dp[i-1][j] + dist(lst,cur)) # move first finger, so second finger remains on j
             dp[i][lst] = min(dp[i][lst], dp[i-1][j] + dist(j,cur))   # move second finger, so second finger becomes the new "first finger"
                                                                                # and now the old "first finger" becomes the new "second finger"
    res = min(dp[N-1])
    return res