[Java] 12ms O(N^2) DP Solution with Clear Explanation
This is my first solution article in Leetcode. If you have any suggestion or question, bring it on! \n\n1. State Representation\nDuring the process of typing, w
This is my first solution article in Leetcode. If you have any suggestion or question, bring it on! \n\n1. State Representation\nDuring the process of typing, we can use the positions of the two fingers to represent the current state.\nFor example,  the word is "LEETCODE".\n\t[5, 7] can represent that the first finger is at "C" and the second finger is at "D".\n**Attention**, the index starts from **1**, because I want to use 0 to denote a finger has not typed anything. Therefore, [0, 4] means that the first finger is not used and the second finger is at "T".\n\n2. Observations\n\t* No After-Effect: When we have already typed some characters, how we move the two fingers after does not affect the distance we have reached so far.\n\t* Over-Lapping Subproblems:  Still use "LEETCODE" as an example. \n\tWhen the first finger is at C and the second finger is at O (**[5, 6]**) , in the next step, we can either move the first finger to "D" or move the second finger to "D". The former state is **[7, 6]** and the latter is **[5, 7]**. As we can see here, both [7, 6] and [5, 7]  can be derived from the [5, 6].\n\t* \tOptimal Substructure: For every state, there must be an optimal way to move the two fingers to reach the state with the shortest distance among all the choices. When we get the shortest distance of  state **dp[i, j]**, we can use it to update the distances of the future states which **dp[i, j]** can reach.\n\n3. How to DP\nI use **dp[i, j] (0 <=i, j <= n)** to represent the shortest distance when the first finger is at the i-th character and the second finger is at the j-th character. Attention, again, the index here starts from 1. 0 means this finger has not been used so far.\nMoreover, for convenience of explanation, I use **dis(i, j)** **(1 <= i, j <= n)** to denote the distance if we move a finger from the i-th character to the j-th character.\n\t* i == j: This is invalid, because we can\'t type the same character twice.\n\t* [1, 0] and [0, 1]: According to the problem, the first character one finger types does not have distance. \n\t\t* dp[1, 0] = 0\n\t\t* dp[0, 1] = 0\n\t* i = 0 or j = 0: This means that we use one single finger to type all the characters so far. \n\t\t* dp[i, 0] = dp[i - 1, 0] + dis(i - 1, i)\n\t\t* dp[0, j] = dp[0, j -1] + dis(j - 1, j)\n\t* i - j >= 2: Such states can only be derived from the state [i - 1, j].  If [i, j] can come from [i, j - 1], it represents that in the current step, we use the second finger to type j-th character. However, since j < i, the j-th character have been typed. Contradiction!\n\t\t* dp[i, j] = dp[i - 1, j] +dis(i - 1, i)\n\t* j - i >= 2: Same reason.\n\t\t* dp[i, j] = dp[i, j - 1] + dis(j - 1, j)\n\t* i - j == 1: This state can be derived from these states: [0, j], [1, j], ..., [j - 1, j].\n\t\t* dp[i, j] = min{dp[0, j], dp[1, j] + dis(1, i), ..., dp[j - 1, j] + dis(j - 1, i)}\n\t* j - i == 1: Same.\n\t\t* dp[i, j] = min{dp[i, 0], dp[i, 1] + dis(1, j), ..., dp[i, i - 1] + dis(i - 1, j)}\n\n```\nclass Solution {\n    \n    public int minimumDistance(String word) {\n        int[][] dist = new int[26][26];\n        for (int i = 0; i < 26; i++)\n            for (int j = 0; j < 26; j++)\n                dist[i][j] = dis(i, j);\n        \n        int n = word.length();\n        char[] c = word.toCharArray();\n        int[][] dp = new int[n + 1][n + 1];\n        dp[0][1] = 0;\n        dp[1][0] = 0;\n        for (int i = 2; i <= n; i++) {\n            dp[0][i] = dp[0][i - 1] + dist[c[i - 2] - \'A\'][c[i - 1] - \'A\'];\n            dp[i][0] = dp[i - 1][0] + dist[c[i - 2] - \'A\'][c[i - 1] - \'A\'];\n        }\n        for (int i = 1; i <= n; i++) {\n            for (int j = 1; j <= n; j++) {\n                if (i == j)\n                    continue;\n                if (j - i >= 2)\n                    dp[i][j] = dp[i][j - 1] + dist[c[j - 2] - \'A\'][c[j - 1] - \'A\'];\n                else if (i - j >= 2)\n                    dp[i][j] = dp[i - 1][j] + dist[c[i - 2] - \'A\'][c[i - 1] - \'A\'];\n                else if (j - i == 1) {\n                    dp[i][j] = dp[i][0];\n                    for (int k = 1; k < i; k++) \n                        dp[i][j] = Math.min(dp[i][k] + dist[c[k - 1] - \'A\'][c[j - 1] - \'A\'], dp[i][j]);\n                }\n                else if (i - j == 1) {\n                    dp[i][j] = dp[0][j];\n                    for (int k = 1; k < j; k++)\n                        dp[i][j] = Math.min(dp[k][j] + dist[c[k - 1] - \'A\'][c[i - 1] - \'A\'], dp[i][j]);\n                }\n            }\n        }\n        int min = Integer.MAX_VALUE;\n        for (int i = 0; i < n; i++) \n            min = Math.min(min, dp[i][n]);\n        return min;\n    }\n    \n    public int dis(int i1, int i2) {\n        int x1 = i1 / 6, y1 = i1 % 6;\n        int x2 = i2 / 6, y2 = i2 % 6;\n        return Math.abs(x1 - x2) + Math.abs(y1 - y2);\n    }\n}\n```
[]