4+ DP Solutions
Update: for the top-down solutions below, I am adding 1 to dp to indicate that we processed that branch. Alternatively, you could initialize dp with -1.\n\n####
> Update: for the top-down solutions below, I am adding `1` to `dp` to indicate that we processed that branch. Alternatively, you could initialize `dp` with `-1`.\n\n#### Top-Down DP\nWe have two choices - type the next character using either left or right index finger. So, we run DFS to find the minimum cost. Without memoisation, the runtime complexity is O(2 ^ n).\n\nThe memoisation dimensions here are quite intuitive - both fingers\' locations and position in the input string. We have 27 locations for each finger, including the initial \'hovering\' state. \n\n```cpp\nint dp[27][27][301] = {[0 ... 26][0 ... 26][0 ... 300] = -1};\nint cost(char from, char to) {\n    return from == 26 ? 0 : abs(from / 6 - to / 6) + abs(from % 6 - to % 6);\n}\nint minimumDistance(string &word, int pos = 0, char left = 26, char right = 26) {\n    if (pos >= word.size()) return 0;\n    if (dp[left][right][pos] == -1) {\n        auto to = word[pos] - \'A\';\n        dp[left][right][pos] = min(cost(left, to) + minimumDistance(word, pos + 1, to, right),\n            cost(right, to) + minimumDistance(word, pos + 1, left, to));\n    }\n    return dp[left][right][pos];\n}\n```\n**Complexity Analysis**\n- Time: O(n * 27 ^ m), where m is the number of fingers. Note that this is a very loose upper bound as we won\'t go through all combinations, as you will see in the next solution.\n- Memory: O(n * 27 ^ m) for memoisation.\n#### Optimized Top-Down DP\nYou can get an intuition that one of two fingers is always located on the previous key. So, we only need to memoise the location of the `other` finger.\n```cpp\nint dp[27][301] = {[0 ... 26][0 ... 300] = -1};\nint cost(char from, char to) {\n    return from == 26 ? 0 : abs(from / 6 - to / 6) + abs(from % 6 - to % 6);\n}\nint minimumDistance(string &word, int pos = 1, char other = 26) {\n    if (pos >= word.size()) return 0;\n    if (dp[other][pos] == -1) {\n        auto to = word[pos] - \'A\', last = word[pos - 1] - \'A\';\n        dp[other][pos] = min(cost(last, to) + minimumDistance(word, pos + 1, other),\n            cost(other, to) + minimumDistance(word, pos + 1, last));\n    }\n    return dp[other][pos];\n}\n```\n**Complexity Analysis**\n- Time: O(n * 27 ^ (m - 1)): where m is the number of fingers.\n- Memory: O(n * 27 ^ (m- 1)) for memoisation.\n#### Bottom-Up DP\nThe first solution above can be easily converted to bottom-up DP. The runtime, however, will be slower, since the top-down solution does not actually go through all combinations of two fingers positions (as we can see from the second solution above).\n```CPP\nint cost(char from, char to) {\n    if (from == 26) return 0;\n    return abs(from / 6 - to / 6) + abs(from % 6 - to % 6);\n}\nint minimumDistance(string word) {\n    int dp[301][27][27] = {};    \n    for (int pos = word.size() - 1; pos >= 0; --pos) {\n        auto to = word[pos] - \'A\';\n        for (int i = 0; i < 27; ++i) {\n            for (int j = 0; j < 27; ++j) {\n                dp[pos][i][j] = min(dp[pos + 1][to][i] + cost(j, to), dp[pos + 1][to][j] + cost(i, to));\n            }\n        }\n    }\n    return dp[0][26][26];\n}\n```\n**Complexity Analysis**\n- Time: O(n * 27 ^ m): where m is the number of fingers.\n- Memory: O(n * 27 ^ m) for tabulation.\n\n#### Memory-Optimized Bottom-Up DP\nAs you can see from the solution above, we are only using tabulation for the last character. Therefore, we only need to tabulate for two characters - current and previous. \n```CPP\nint cost(char from, char to) {\n    if (from == 26) return 0;\n    return abs(from / 6 - to / 6) + abs(from % 6 - to % 6);\n}\nint minimumDistance(string word) {\n    int dp[2][27][27] = {};    \n    for (int pos = word.size() - 1; pos >= 0; --pos) {\n        auto to = word[pos] - \'A\';\n        for (int i = 0; i < 27; ++i) {\n            for (int j = 0; j < 27; ++j) {\n                dp[pos % 2][i][j] = min(dp[(pos + 1) % 2][to][i] + \n                    cost(j, to), dp[(pos + 1) % 2][to][j] + cost(i, to));\n            }\n        }\n    }\n    return dp[0][26][26];\n}\n```\n**Complexity Analysis**\n- Time: O(n * 27 ^ m): where m is the number of fingers.\n- Memory: O(27 ^ m) for tabulation.\n\n#### The "Plus" Solution\nSolutions 1, 3 and 4 above is how you might approach any DP problem during the interview:\n- Start with DFS\n- Add memoisation\n- Using your top-down solution, come up with a bottom-up one\n- Optimize memory for the bottom-up solution\n\nSolution 2 above uses the specific problem constraint to optimize the runtime. We used the fact that one of the fingers would be always on the previous letter, and only passed the position of the *other* finger. This would be a big plus if you could get such insight during the interview.\n\nIntuitively, there should exist a bottom-up version of solution 2, where we can optimize the memory even further than in solution 4 above. I could not, however, easily come up with such solution. The closest I saw here is [Solution 2 in this post by Lee215](https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/discuss/477652/JavaC%2B%2BPython-DP-Solution-O(1)-Space).\n\nThat solution, however, requires even deeper insight to come up with, yet alone to understand :) Perhaps, we could come up with an easier to understand solution. Please let me know if you have any ideas!
[]