Java 3D DP SOLUTION LOOPING FORWARDS WITH A CLEAR DEFINITION OF DP[i][j][k]
\n\nclass Solution {\n    public int minimumDistance(String word) {\n        \n        //dp[i][j][k] := minimum distance to type word[0...k] with left finger en
\n```\nclass Solution {\n    public int minimumDistance(String word) {\n        \n        //dp[i][j][k] := minimum distance to type word[0...k] with left finger ending @ i, right finger ending @ j\n        int[][][] dp = new int[26][26][word.length()];\n        \n        //key idea: need to go through all possibilities (and save progress via memoization)\n        \n        //init\n        //need to populate all entries w/ big number (to represent infinity) \n        for(int k = 0; k < word.length(); k++){\n            for(int i = 0; i < 26; i++) {\n                for(int j = 0; j < 26; j++) {\n                    dp[i][j][k] = Integer.MAX_VALUE/2; // div. by 2 to prevent overflow\n                }\n            }\n        }\n        \n        //deal with base case\n        int charK = word.charAt(0) - \'A\'; //the translation from char -> 0..25\n        for(int i = 0; i < 26; i++) {\n            dp[charK][i][0] = 0; //right finger on first letter of word, other finger on everything else \n            dp[i][charK][0] = 0; //left finger on first letter of word, other finger on everything else\n        }\n        \n        \n        int res = Integer.MAX_VALUE;\n        \n        for(int k = 1; k < word.length(); k++) {\n            \n            charK = word.charAt(k) - \'A\';\n            //in the following loops, find BEST possible way to end up w/ ONE finger at charK\n            \n            for(int i = 0; i < 26; i++) {//plant i as either the left or right finger\n                                         //ex, i = 0, so plant left finger on A (or right finger on A)\n                                         //now, GIVEN left finger on A, explore right finger coming FROM every letter to charK (same idea for GIVEN right finger on A, "")\n                                         //key idea: explore all possibilities. You know that one of the fingers has to END up on charK, BUT the other finger can be on ANYTHING, and the finger which ends up on charK could\'ve come from ANYTHING!\n                \n                for(int j = 0; j < 26; j++) {//explore opp finger coming from SOME letter -> charK\n                    \n                    //i is planted as right finger\n                    //left finger ends up at charK\n                    dp[charK][i][k] = Math.min(dp[charK][i][k], dp[j][i][k-1] + d(j, charK)); //either already have optimal answer, or found some j from which the left finger is coming from -> charK such that have better answer\n                    \n                    //i is planted as left finger\n                    //right finger ends up at charK\n                    dp[i][charK][k] = Math.min(dp[i][charK][k], dp[i][j][k-1] + d(j,charK));\n                    \n                }\n                \n                //at the last layer\n                if(k==word.length()-1){\n                    //one of the fingers has to be @ charK\n                    res = Math.min(res,dp[i][charK][k]);\n                    \n                    //following not necessary b/c dp[i][charK][k] should == dp[charK][i][k] \n                    //res = Math.min(res, dp[charK][i][k]);\n                                                            \n                }\n            }\n        }\n        \n        return res;\n        \n    }\n    \n    //calc\'s distance between "char" a and b\n    private int d(int a, int b) {\n        return Math.abs(a / 6 - b / 6) + Math.abs(a % 6 - b % 6);\n    }\n}\n```
[]