From 3D DP to 2D and 1D; explanation is easy to understand
The best straighforward solution is just the DFS + DP, which is in fact a 3D DP solution. \n\njava\nint[][][] memo;\npublic int minimumDistance_3d(String word) 
The best straighforward solution is just the DFS + DP, which is in fact a 3D DP solution. \n\n```java\nint[][][] memo;\npublic int minimumDistance_3d(String word) {\n\tif (word == null) return 0;\n\tint length = word.length();\n\tif (length == 1 || length ==2) return 0;\n\tmemo = new int[length][27][27];\n\treturn helper(word, 0, 26, 26);\n}\n\nprivate int helper(String word, int index, int lastLeft, int lastRight) {\n\tif (index >= word.length()) return 0;\n\tif (memo[index][lastLeft][lastRight] == 0) {\n\t\tint charIndex = word.charAt(index) - \'A\';\n\t\tmemo[index][lastLeft][lastRight] = Math.min(\n\t\t\tgetDistance(lastLeft, charIndex) + helper(word, index + 1, charIndex, lastRight),\n\t\t\tgetDistance(lastRight, charIndex) + helper(word, index + 1, lastLeft, charIndex));\n\t}\n\n\treturn memo[index][lastLeft][lastRight];\n}\n\nprivate int getDistance(int from, int to) {\n\tif (from == 26) return 0;\n\treturn Math.abs(from / 6 - to / 6) + Math.abs(from % 6 - to % 6);\n\n}\n```\n\t\nSince it is using the DFS backtracking, this solution should be easy to understand and implement. You will later find that, after inputing one char from the string, one hand will remain unchanged, and it indicates that we do not need to record both `lastLeft` and `lastRight` status. With the param `index`, we can easily know the last status of one hand, and we track another status in param `other`. Thus, we can implement a 2D solution:\n\n```java\nint[][] dp;\npublic int minimumDistance_2d_top_bottom(String word) {\n\tif (word == null) return 0;\n\tint length = word.length();\n\tif (length == 1 || length ==2) return 0;\n\tdp = new int[length][27];\n\treturn helper2(word, 1, 26); // note: we can start from 1 (think why)\n}\n\nprivate int helper2(String word, int index, int other) {\n\tif (index >= word.length()) return 0;\n\tif (dp[index][other] == 0) {\n\t\tint curCharIndex = word.charAt(index) - \'A\', preCharIndex = word.charAt(index - 1) - \'A\';\n\t\tdp[index][other] = Math.min(\n\t\t\tgetDistance(preCharIndex, curCharIndex) + helper2(word, index + 1, other),\n\t\t\tgetDistance(other, curCharIndex) + helper2(word, index + 1, preCharIndex)\n\t\t);\n\t}\n\treturn dp[index][other];\n}\n```\n\nAll of the solutions above are top-bottom, as we want to associate them with the DFS. You wil find that, in the 2D top-bottom solution, the current DP value in func `helper2` depends on the values of the next line of DP array; in other words, `dp[index][...]` will depend on `dp[index+1][...]`. Thus, a top-bottom solution (pure DP) could be easily implemented.\n\n```java\npublic int minimumDistance_2d_bottom_up(String word) {\n        if (word == null) return 0;\n        int length = word.length();\n        if (length == 1 || length ==2) return 0;\n        int[][] dpArray = new int[length][27];\n        for (int i = length - 1; i >= 1; i--) {  // we don\'t need the value when i = 0;\n            int curCharIndex = word.charAt(i) - \'A\', preCharIndex = word.charAt(i - 1) - \'A\';\n            for (int j = 0; j < 27; j++) {\n                dpArray[i][j] = Math.min(\n                    getDistance(preCharIndex, curCharIndex) + (i == length - 1? 0: dpArray[i+1][j]),\n                    getDistance(j, curCharIndex) + (i == length - 1? 0: dpArray[i+1][preCharIndex])\n                );\n            }\n        }\n        return dpArray[1][26];\n    }\n```\n\nOnce again, we found that `dp[index][...]` will depend on and ONLY on  `dp[index+1][...]`. Thus, we do not need to track all values in the dp array.\n\n```java\npublic int minimumDistance(String word) {\n\tif (word == null) return 0;\n\tint length = word.length();\n\tif (length == 1 || length ==2) return 0;\n\tint[] dpArray = new int[27];\n\tfor (int i = length - 1; i >= 1; i --) {\n\t\tint[] tmp = new int[27];\n\t\tint curCharIndex = word.charAt(i) - \'A\', preCharIndex = word.charAt(i - 1) - \'A\';\n\t\tfor (int j = 0; j < 27; j++) {\n\t\t\ttmp[j] = Math.min(\n\t\t\t\tgetDistance(preCharIndex, curCharIndex) + (i == length - 1? 0: dpArray[j]),\n\t\t\t\tgetDistance(j, curCharIndex) + (i == length - 1? 0: dpArray[preCharIndex])\n\t\t\t);\n\t\t}\n\t\tdpArray = tmp;\n\t}\n\treturn dpArray[26];\n}\n```\n\nIn this solution, we only have 2 1D arrays with fixed length (O(1) space); time complexity is O(length).\n\t
[]