python - 最短距离两指打字问题的动态规划解决方案

Question

我正在努力让自己更好地了解 动态规划 ，并希望通过尝试解决以下问题来做到这一点(供引用 here's a solution)。

You have a keyboard layout as shown above in the XY plane, where each English uppercase letter is located at some coordinate, for example, the letter A is located at coordinate (0,0), the letter B is located at coordinate (0,1), the letter P is located at coordinate (2,3) and the letter Z is located at coordinate (4,1).

Given the string word, return the minimum total distance to type such string using only two fingers. The distance between coordinates (x1,y1) and (x2,y2) is |x1 - x2| + |y1 - y2|.

Note that the initial positions of your two fingers are considered free so don't count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.

例如对于输入词 "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(就空间而言)动态规划解决方案。我在网上找到了解决这个问题的1D和2D解决方案，但我觉得它们太难理解了，所以我希望从3D开始，逐渐了解更有效的解决方案。
这个问题的 3D DP 公式是什么？这个问题有特别的名字吗？
我理解问题的递归性质，但我正在努力制定一个 简单 自下而上的解决方案(例如在 3D 中)。

Answer 1

一个相当简单的 3-D 动态规划方法如下:

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函数，我们声明一个动态规划表 dp[N+1][26][26] ，让我们存储在单元格 dp[i][j][k]输入字符串中直到第 i 个字符(但不包括第 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