[Java] 3D/2D Top-Down/Memoization DP Solution
Would like to share my thoughts from initial solution and then optimized gradually:\n\n1. First thoughts: 3D DP with Memoization:\n\nclass Solution {\n    publi
Would like to share my thoughts from initial solution and then optimized gradually:\n\n1. First thoughts: 3D DP with Memoization:\n```\nclass Solution {\n    public int minimumDistance(String word) {\n        int n = word.length();\n        int[][][] dp = new int[n][27][27];\n        char[] arr = word.toCharArray();\n        int res = Integer.MAX_VALUE;\n        for (int i = 0; i < 27; i++) {\n            for (int j = i; j < 27; j++) {\n                res = Math.min(res, helper(arr, 0, i, j, dp));\n            }\n        }\n        return res;\n    }\n    \n    private int helper(char[] word, int k, int i, int j, int[][][] dp) {\n        if (k == word.length) return 0;\n        if (dp[k][i][j] > 0) return dp[k][i][j];\n        \n        int cost = Math.min(helper(word, k + 1, word[k] - \'A\', j, dp) + cost(i, word[k] - \'A\'), helper(word, k + 1, i, word[k] - \'A\', dp) + cost(j, word[k] - \'A\'));\n        return dp[k][i][j] = cost;\n    }\n    \n   private int cost(int from, int to) {\n        if (from == 26) return 0;\n        return Math.abs(from/6 - to/6) + Math.abs(from%6 - to%6);\n    }\n}\n```\n2. Optimized to 2D DP with Memoization:\nwith observation, one of the pointer can be inferred from current position ``k``: thus DP can be optimized to 2D, note that the initial ``k = 1``\n```\nclass Solution {\n    public int minimumDistance(String word) {\n        int n = word.length();\n        int[][] dp = new int[n][27];\n        char[] arr = word.toCharArray();\n        int res = Integer.MAX_VALUE;\n        for (int i = 0; i < 27; i++) {\n            res = Math.min(res, helper(arr, 1, i, dp));\n        }\n        return res;\n    }\n    \n    private int helper(char[] word, int k, int i, int[][] dp) {\n        if (k >= word.length) return 0;\n        if (dp[k][i] > 0) return dp[k][i];\n        int cur = word[k] - \'A\';\n        int cost = Math.min(helper(word, k+1, i, dp) + cost(word[k-1] - \'A\', cur), helper(word, k+1, word[k-1] - \'A\', dp) + cost(i, cur));\n        return dp[k][i] = cost;\n    }\n    \n    private int cost(int from, int to) {\n        if (from == 26) return 0;\n        return Math.abs(from/6 - to/6) + Math.abs(from%6 - to%6);\n    }\n}\n```\n\nThen the following is easy, converted Memoization to Top-Down following its topological order:\n3. 3D Top-Down DP\n```\nclass Solution {\n    public int minimumDistance(String word) {\n        int n = word.length();\n        int[][][] dp = new int[n+1][27][27];\n        char[] arr = word.toCharArray();\n        for (int k = n - 1; k >= 0; k--) {\n            for (int i = 0; i < 27; i++) {\n                for (int j = 0; j < 27; j++) {\n                    dp[k][i][j] = Math.min(dp[k+1][arr[k]-\'A\'][j] + cost(i, arr[k] - \'A\'), dp[k+1][i][arr[k]-\'A\'] + cost(j, arr[k] - \'A\'));\n                }\n            }\n        }\n        return dp[0][26][26];\n    }\n    \n     private int cost(int from, int to) {\n        if (from == 26) return 0;\n        return Math.abs(from/6 - to/6) + Math.abs(from%6 - to%6);\n    }\n}\n```\n\n4. 2D Top-Down DP\n```\nclass Solution {\n    public int minimumDistance(String word) {\n        int n = word.length();\n        int[][] dp = new int[n+1][27];\n        char[] arr = word.toCharArray();\n        for (int k = n - 1; k > 0; k--) {\n            for (int i = 0; i < 27; i++) {\n                int cur = arr[k] - \'A\';\n                dp[k][i] = Math.min(dp[k+1][arr[k-1]-\'A\'] + cost(i, cur), dp[k+1][i] + cost(arr[k-1]-\'A\', cur));\n            }\n        }\n        return dp[1][26];\n    }\n\n    private int cost(int from, int to) {\n        if (from == 26) return 0;\n        return Math.abs(from/6 - to/6) + Math.abs(from%6 - to%6);\n    }\n}\n```\n\nthere is also 1D DP solution from 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
[]