A good 3d DP practice - my DP note
This problem is a good practice for 3d DP. Even though I got TLE by using DFS in the contest, I went through three different DP solutions posted by others and h
This problem is a good practice for 3d DP. Even though I got TLE by using DFS in the contest, I went through three different DP solutions posted by others and here is my code and explanation.\n\nIn all of these solutions, I have the same mapping between numbers and chars:\n```\nfree the finger -> 0\nA -> 1\nB -> 2\n...\nZ -> 26\n```\nTherefore, the dimension of dp arrays is 27.\n\nIn all of these solutions, ```dp[i][j][k]``` means:\n```\ni: current step is the ith step; current char to be considered is word[i]\nj: finger1 is at letter ord(\'A\')+j-1\nk: finger2 is at letter ord(\'A\')+k-1\n```\n\n**Method1: DFS without memorization**\nThough DFS without memorization gets TLE, it gives us some hints to find the DP sub-problem. In the ```move()``` function, we have ```finger1, finger2, i, dist``` four parameters. We try to move finger1 and finger2 to ```word[i]``` alternatively in the recursion, and once we get to the end of ```word```, we update the minimum distance.\n\nIn this method, we do not cache the result for state ```finger1, finger2, i```, and when we get to the same state, we need to calculate the cost again, so it gets TLE. **However, it implies that the three DP states should be ```finger1, finger2, i```.**\n\n```\nclass Solution:\n    def minimumDistance(self, word: str) -> int:\n        def getXY(letter):\n            m=(ord(letter)-ord(\'A\'))//6\n            n=(ord(letter)-ord(\'A\'))%6\n            \n            return m, n\n        \n        n=len(word)\n        memo=set()\n        \n        finger1=(-1, -1)\n        finger2=(-1, -1)\n        \n        self.res=float(\'inf\')\n        def move(finger1, finger2, i, dist):\n            if i==len(word):\n                self.res=min(self.res, dist)\n                return\n            \n            x, y=getXY(word[i])\n            \n            if finger1!=(-1, -1):\n                move((x, y), finger2, i+1, dist+abs(x-finger1[0])+abs(y-finger1[1]))\n            else:\n                move((x, y), finger2, i+1, dist)\n            \n            if finger2!=(-1, -1):\n                move(finger1, (x, y), i+1, dist+abs(x-finger2[0])+abs(y-finger2[1]))\n            else:\n                move(finger1, (x, y), i+1, dist)\n        \n        move(finger1, finger2, 0, 0)\n        return self.res\n```\n\n**Method 2: DFS with memorization (top-down DP)**\nThis method is proposed by https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/discuss/477659/4%2B-DP-Solutions\n\nI noticed that for this problem, starting to go through the ```word``` from the left to right has the same cost as from the right to left, if we imagine the last step is to free two fingers. The first dimension of sub-problem is ```word[i:]```. Therefore, we can start to fill the dp array from ```word[i+1]``` to ```word[i]```. This can be done recursively. \n\n```\ndp=[[[float(\'inf\')]*27 for _ in range(27)] for _ in range(len(word))]\n\ndef dist(pos_a, pos_b):\n    if pos_a==0 or pos_b==0:\n        return 0\n\n    return abs((pos_a-1)//6-(pos_b-1)//6)+abs((pos_a-1)%6-(pos_b-1)%6)\n\ndef helper(finger1, finger2, i):\n    if i==len(word):\n        return 0\n\n    if dp[i][finger1][finger2]<float(\'inf\'):\n        return dp[i][finger1][finger2]\n\n    cur=ord(word[i])-ord(\'A\')+1\n    dp[i][finger1][finger2]=min(dist(finger1, cur)+helper(cur, finger2, i+1), dist(finger2, cur)+helper(finger1, cur, i+1))\n\n    return dp[i][finger1][finger2]\n\nhelper(0, 0, 0)\n\nres=float(\'inf\')\nfor i in range(27):\n    for j in range(27):\n        res=min(res, dp[0][i][j])\n\nreturn res\n```\n\n**Method 3: bottom up DP**\nSince starting from right has the same cost as starting from left, we can also get the result for ```word[i]``` according to ```word[i-1]```. This method is proposed by https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/discuss/478075/Java-DP-Solution-O(26*26*N)-Time-Complexity\n\nIn the ```for``` loop, we do:\n```\n# move finger1\ndp[i][cur_pos][k]=min(dp[i][cur_pos][k], dp[i-1][j][k]+dist(j, cur_pos))\n\n# move finger2\ndp[i][j][cur_pos]=min(dp[i][j][cur_pos], dp[i-1][j][k]+dist(k, cur_pos))\n```\n\nThe reason that we have ```min()``` in the for loop above is, **moving finger1 and moving finger2 might update the same ```dp[i][j][k]```, so we need to get the minimum.**\n\nThe code snippet above means that if the char of finger in the last step is ```j``` or ```k```, we should add ```dist(j, cur_pos)``` or ```dist(k, cur_pos)``` to current cost to move the finger to current char ```word[i]```. \n\n**We do not need to care about what is ```word[i-1]``` because we initiate the dp array with ```float(\'inf\')```, and only those cells representing the existed chars in ```word``` will be activated (less than ```infinite```).** \n\n```\ndef dist(pos_a, pos_b):\n  if pos_a==0 or pos_b==0:\n      return 0\n\n  return abs((pos_a-1)//6-(pos_b-1)//6)+abs((pos_a-1)%6-(pos_b-1)%6)\n\ndp=[[[float(\'inf\')]*27 for _ in range(27)] for _ in range(len(word))]\n\nfirst=ord(word[0])-ord(\'A\')+1\ndp[0][0][first]=0\ndp[0][first][0]=0\n\nfor i in range(1, len(word)):\n    cur_pos=ord(word[i])-ord(\'A\')+1\n\n    for j in range(27):\n        for k in range(27):\n            # move finger1\n            dp[i][cur_pos][k]=min(dp[i][cur_pos][k], dp[i-1][j][k]+dist(j, cur_pos))\n\n            # move finger2\n            dp[i][j][cur_pos]=min(dp[i][j][cur_pos], dp[i-1][j][k]+dist(k, cur_pos))\n\nres=float(\'inf\')\nfor i in range(27):\n    for j in range(27):\n        res=min(res, dp[len(word)-1][i][j])\nreturn res\n```\n\n**Method 4: optimization of method 3**\nThis method is proposed by lee215. https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/discuss/477652/JavaC%2B%2BPython-1D-DP-O(1)-Space\n\nIf you understand the method 3, method 4 becomes very intuitive. **How to keep track of the "activated cells in the dp array"?** Rather than using array, we can use dictionary! The key of dictionary is the status of two fingers, the value is the accumulated distance. \n\nWe use ```last``` and ```cur``` to denote the dp dictionary in the last time step and current time step respectively. Again, the reason why we use ```min()``` here because we might calculate a status twice.\n\n```\nlast={} # the dp dictionary in last time step\ncur={} # the dp dictionary in current time step\n\nn=len(word)\n\ndef dist(pos_a, pos_b):\n    if pos_a==0 or pos_b==0:\n        return 0\n\n    return abs((pos_a-1)//6-(pos_b-1)//6)+abs((pos_a-1)%6-(pos_b-1)%6)\n\nfirst=ord(word[0])-ord(\'A\')+1\n\nlast[(0, first)]=0\nlast[(first, 0)]=0\n\nfor i in range(1, n):\n    c=ord(word[i])-ord(\'A\')+1\n\n    for a, b in last:\n        # move finger1\n        # 10000 is the same as infinite\n        cur[c, b]=min(cur.get((c, b), 10000), last[a, b]+dist(a, c))\n        # move finger2\n        cur[a, c]=min(cur.get((a, c), 10000), last[a, b]+dist(b, c))\n\n    last=cur\n    cur={}\n\nreturn min(last.values())\n```\n\n
['Dynamic Programming']