Straightforward 3 steps from Simple TLE DFS to AC DP solution with explanation
First I came up with this brute-force DFS solution:\n\nIdea is because we know finger 1 will always start with index 0 of word, we can simply use a for loop to 
First I came up with this brute-force DFS solution:\n\nIdea is because we know finger 1 will always start with index 0 of word, we can simply use a for loop to try to compute total costs as if we start finger 2 at index 1, or 2, or 3, ..., until word.length() - 1, and get the min of them.\n\naCosts[i - 1] stores the cost for finger 1 to type until index i - 1, we need this cost because we noticed that if we start finger 2 at index i, then finger 1 will have to at least type all chars until index i - 1.\n\nEach dfs call will try to use finger 1 to type next char as well as use finger 2 to type next char, and then return min cost between these two.\n\n```\nclass Solution {\n    public int minimumDistance(String word) {\n        int[] aCosts = new int[word.length()];\n        for (int i = 1; i < aCosts.length; i++) aCosts[i] = aCosts[i - 1] + dist(word.charAt(i - 1), word.charAt(i));\n        int res = Integer.MAX_VALUE;\n        for (int i = 1; i < word.length(); i++) {\n            res = Math.min(res, dfs(word.charAt(i - 1), aCosts[i - 1], word.charAt(i), 0, i + 1, word));\n        }\n        return res;\n    }\n    \n    private int dfs(char a, int aCost, char b, int bCost, int start, String word) {\n        if (start == word.length()) return aCost + bCost;\n        char c = word.charAt(start);\n        int aDiff = dist(a, c);\n        int bDiff = dist(b, c);\n        return Math.min(dfs(c, aCost + aDiff, b, bCost, start + 1, word), dfs(a, aCost, c, bCost + bDiff, start + 1, word));\n    }\n    \n    private int dist(char a, char b) {\n        int i = a - \'A\', j = b - \'A\';\n        return Math.abs(i / 6 - j / 6) + Math.abs(i % 6 - j % 6);\n    }\n}\n```\n\nAfter submitting this simple DFS solution, I got TLE as expected, because we are visiting too many overlapped subproblems or in other words too many dfs calls to solve the same subproblem.\n\nThe first thought that come to our mind should be using memoization to store results for subproblems so in the consecutive visits to the same subproblem we can just simply return the result.\n\nWhat I did here is to first reduce the subproblem variants, or in other words reduce the number of input variables to our dfs call so that we can have more subproblem overlaps.\n\n```\nclass Solution {\n    public int minimumDistance(String word) {\n        int[] aCosts = new int[word.length()];\n        for (int i = 1; i < aCosts.length; i++) aCosts[i] = aCosts[i - 1] + dist(word.charAt(i - 1), word.charAt(i));\n        int res = Integer.MAX_VALUE;\n        for (int i = 1; i < word.length(); i++) {\n            res = Math.min(res, aCosts[i - 1] + dfs(word.charAt(i - 1), word.charAt(i), i + 1, word));\n        }\n        return res;\n    }\n    \n    private int dfs(char a, char b, int start, String word) {\n        if (start == word.length()) return 0;\n        char c = word.charAt(start);\n        int aDiff = dist(a, c);\n        int bDiff = dist(b, c);\n        return Math.min(aDiff + dfs(c, b, start + 1, word), bDiff + dfs(a, c, start + 1, word));\n    }\n    \n    private int dist(char a, char b) {\n        int i = a - \'A\', j = b - \'A\';\n        return Math.abs(i / 6 - j / 6) + Math.abs(i % 6 - j % 6);\n    }\n}\n```\n\nDid you notice now our dfs calls will only depend on 3 input variables? char a, char b, and int start, they correspond to most recently typed char by finger 1, most recently typed char by finger 2, and next starting index we try to process in string word. \n\nNow we can just build a 3D array to store all possible combinations from these 3 input variables. char a can be in range from A to Z, char b can be in range from A to Z, int start can be in range from 0 to word.length() - 1, so that our 3D array could be ``int[][][] dp = new int[26][26][word.length()];``.\n\n```\nclass Solution {\n    public int minimumDistance(String word) {\n        int[] aCosts = new int[word.length()];\n        for (int i = 1; i < aCosts.length; i++) aCosts[i] = aCosts[i - 1] + dist(word.charAt(i - 1), word.charAt(i));\n        int res = Integer.MAX_VALUE;\n        int[][][] dp = new int[26][26][word.length()];\n        for (int i = 1; i < word.length(); i++) {\n            res = Math.min(res, aCosts[i - 1] + dfs(word.charAt(i - 1), word.charAt(i), i + 1, word, dp));\n        }\n        return res;\n    }\n    \n    private int dfs(char a, char b, int start, String word, int[][][] dp) {\n        if (start == word.length()) return 0;\n        if (dp[a - \'A\'][b - \'A\'][start] != 0) return dp[a - \'A\'][b - \'A\'][start];\n        char c = word.charAt(start);\n        int aDiff = dist(a, c);\n        int bDiff = dist(b, c);\n        int res = Math.min(aDiff + dfs(c, b, start + 1, word, dp), bDiff + dfs(a, c, start + 1, word, dp));\n        dp[a - \'A\'][b - \'A\'][start] = res;\n        return res;\n    }\n    \n    private int dist(char a, char b) {\n        int i = a - \'A\', j = b - \'A\';\n        return Math.abs(i / 6 - j / 6) + Math.abs(i % 6 - j % 6);\n    }\n}\n```\n\nBy doing these 3 steps we now have an accepted DP solution! I hope this helps :)\n
[]