Detailed explanation on optimizing a 3D/2D DP to 1D
Intuitive enough as a 3D DP\n\nIt is not hard to come up with an intuition to use DP to solve this problem. \n\nGiven a string word, we can define a state the  
# ***Intuitive enough as a 3D DP***\n\nIt is not hard to come up with an intuition to use DP to solve this problem. \n\nGiven a string `word`, we can define a *state* the  that `dp[i][j][k]`  represents **the minimum distance to type until `word[k]`, left finger is at char `i` and right finger is at char `j`**. That is, **dim 0 for left finger, and dim 1 for right finger.**\n\nThen we can think about how we move our fingers from `word[k-1]` to `word[k]` to keep the minimum value. Intuitively again, we have two options: move left finger or move right finger. \n\nIf we move one finger to the target character, we have two simple inferences:\n\n1. this finger must be at the corresponding index of `word[k]` (denoted as `idx`) after moving;\n2. the other finger is at the original place. That\'s say, for left finger, if we want to move to `dp[idx][j]`, **we can only move from the same column `dp[i][j] for i from \'A\' to \'Z\'`,** and the same row for right finger\n\nTherefore, we have the transition\n\n`dp[idx][j][k] = min(dp[i][j][k-1] + dist(i, idx)) for i from \'A\' to \'Z\'` (`j` is fixed), and\n`dp[i][idx][k] = min(dp[i][j][k-1] + dist(j, idx)) for j from \'A\' to \'Z\'` (`i` is fixed)\n\nWe can see that `k` is only related to `k-1`, thus we can easily optimize it to a 2D DP, and the following is the code. I append a dummy character at the end to represent a start case, where the distance from it to any other char is 0.\n\n\n```python\nclass Solution:\n\t\n\t# This solution gets TLE\n\t\n    def minimumDistance(self, word: str) -> int:\n        dp = [[float(\'inf\')] * 27 for _ in range(27)]\n        \n        dp[-1][-1] = 0\n        \n        for ch in word:\n            new_dp = [[float(\'inf\')] * 27 for _ in range(27)]\n            \n            idx = ord(ch) - ord(\'A\')\n            for j in range(27):\n                new_dp[idx][j] = min(dp[i][j] + dist(i, idx) for i in range(27))\n            \n            for i in range(27):\n                new_dp[i][idx] = min(dp[i][j] + dist(idx, j) for j in range(27))\n            \n            dp = new_dp\n        \n        return min(min(row) for row in dp)\n\ndef dist(i, j): \n    if i == 26 or j == 26: # last dummy index\n        return 0\n\n    return abs(i // 6 - j // 6) + abs(i % 6 - j % 6)\n```\n\nHowever, this solution gets TLE...\n\n  \n  \n  \n# ***Update only one row and one column but building a matrix?!***\n\nHere is the visualization on how the above algorithm works. Every time only the row and the column of the current character has values, and the other place are all `inf`. Why can\'t we just maintain two lists to represent the transition?\n\n![image](https://assets.leetcode.com/users/k_kkkyle/image_1579230434.png)\n\n- **What\'s the transition if we have only two lists**\n\nSay we have two lists, `dp_left` and `dp_right`, and the last character was at `prev_idx` and current character is `idx`. Take a look at the figure, and take `dp_left` as example.\n\nWe "move" the `dp_left` bar from `prev_idx = 26` to `idx = 2` ("C"), `dp[idx][j]` should be the minimum value of `dp[i][j] + dist(i, idx)` **along the row `j`**.\n\nHowever, we observe that **expect _column_ `prev_idx`, the rest columns have values only at _row_ `prev_idx`**.\n\nThat\'s say, **for all other columns, the new dp value is the prev dp value + the distance between prev index and new index.**\n\nAnd for column `prev_idx` , the transtion will be the minimum value + the distance in **the other dp list**.\n\nThe code block for this transition is\n\n```python\nd = dist(prev_idx, idx)\n            \nleft_min = min(dp_left[i] + dist(i, idx) for i in range(27))\nright_min = min(dp_right[i] + dist(i, idx) for i in range(27))\n\nfor i in range(27):\n\tdp_left[i] = dp_left[i] + d if i != prev_idx else right_min\n\tdp_right[i] = dp_right[i] + d if i != prev_idx else left_min \n```\n\nAnd the full code is as follows, finally we return the min value in `dp_left` and `dp_right`. \n\n```python\nclass Solution:\n\n\t# This solution takes 196 ms and beats ~95%\n\n    def minimumDistance(self, word: str) -> int:\n        dp_left = [float(\'inf\')] * 27\n        dp_right = [float(\'inf\')] * 27\n        \n        dp_left[-1] = dp_right[-1] = 0\n        \n        prev_idx = 26\n        for ch in word:\n            idx = ord(ch) - ord(\'A\')\n            d = dist(prev_idx, idx)\n            \n            left_min = min(dp_left[i] + dist(i, idx) for i in range(27))\n            right_min = min(dp_right[i] + dist(i, idx) for i in range(27))\n            \n            for i in range(27):\n                dp_left[i] = dp_left[i] + d if i != prev_idx else right_min\n                dp_right[i] = dp_right[i] + d if i != prev_idx else left_min \n            \n            dp_left[idx] = dp_right[idx] = min(dp_left[idx], dp_right[idx])\n            prev_idx = idx\n\n        return min(min(dp_left), min(dp_right))         \n\t\t\ndef dist(i, j): \n    if i == 26 or j == 26: # last dummy index\n        return 0\n\n    return abs(i // 6 - j // 6) + abs(i % 6 - j % 6)\n```\n  \n  \n  \n# ***Two dp lists are the same ?!***\n\nIt seems that `dp_left` and `dp_right` are always the same thing, right?\nI test this on several cases and this is true!\n\nAn extremely long arbitrary case\n\n"KXGJRDQYJCDRTJXBHDVFOFFOIWFOWSARMADDJCUYMGIXMHOUTQRLFNUZASNTHJLQKPUYXOXWILI\nYFFHOKUALPTZWJVHADOXQFGMWTKREBPNOZOLAGSGCPEVCXQWVRMTIGCNARPWXKXAGTJYYZNOW\nQWJCBCLMUNMZUWYUYHJPMRAUNUJVPEMVNMWYSXTJPRLJNSUYFLBNOOJCVHKHMATKEFPCYDFTB\nHUFAUQVNVNFJMOJRBFPFDVDPXJXZJJMBSIK"\n\n```\ndp_left = [545, 502, 567, 518, 577, 524, 646, 555, 504, 505, 576, 583, 505, 538, 533, 518, 547, 530, 500, 557, 548, 519, 600, 511, 561, 506, 800]\ndp_right = [545, 502, 567, 518, 577, 524, 646, 555, 504, 505, 576, 583, 505, 538, 533, 518, 547, 530, 500, 557, 548, 519, 600, 511, 561, 506, 800]\n```\n\nHere is a simple proof by induction:\n\n1. `dp_left` and `dp_right` are the same at base case\n2. the transition are the same, because the min value of the two lists are identical, and all other values are identical\n3. thus `dp_left`\\_{t + 1} == `dp_right`\\_{t + 1} for any t in [0,k]\n\nSo finally we come to the simplest solution which you might find in many other solutions, we just merge the two lists as one\n\n```python\n\n# this solution takes 108ms beats 99%\n\nclass Solution:\n    def minimumDistance(self, word: str) -> int:\n        dp = [float(\'inf\')] * 27\n        dp[-1] = 0\n        \n        prev_idx = 26\n        for ch in word:\n            idx = ord(ch) - ord(\'A\')\n            d = dist(prev_idx, idx)\n            \n            mindist = min(dp[i] + dist(i, idx) for i in range(27))\n            \n            for i in range(27):\n                dp[i] = dp[i] + d if i != prev_idx else mindist\n\n            prev_idx = idx\n\n        return min(dp)        \n\ndef dist(i, j): \n    if i == 26 or j == 26: # last dummy index\n        return 0\n\n    return abs(i // 6 - j // 6) + abs(i % 6 - j % 6)\n```\n  \n  \n  \n# ***Change code is simple... but what does it mean?***\n\nWe can prove that why two lists are the same, but it\'s not easy to get an intuition of that. Here is my points for digging into why we can maintain only one dp array to represent two fingers.\n\n1. What does the state mean?\n\t- It means, if we desired to move to `word[k]`, **the cost of either left finger or right finger**.\n\t- We need to explain why the state for two fingers are the same\n2. two fingers are symmetric\n\t- It\'s intuitive. We can imagine that if two finger are at the same place, then moving either finger are the same.\n\t- Then it comes to an inference due to the symmetry: at any time, \n\t\twhen left finger is going to move, the state of right finger\n\t\t is the same as \n\t\twhen right finger is going to move, the state of left finger\n\t\t(I know it\'s confusing...)\n\t- Think about BFS: we start from `(0,0)` (place of left and right fingers) to `[(1, 0), (0,1)]`, where  `[(1, 0), (0,1)]` are the same because of they\'re symmetric, and moving `(1,0)` to `(2,0)` will be the same as moving `(0,1)` to `(0,2)`... and so on\n\t- Thus we can introduce induction again to prove that **for any state left finger is at, right finger should have the same state**\n\nThe intuition for this 1D 1-array dp, still, may be not intuitive, it will be great help if someone can give a better explanation!\n\n\n\n\n\n\n\n
[]