C++ | Intuitive | Top down DP | Easy to understand
\nclass Solution {\npublic:\n\tint n;\n\tvector<vector<vector<int>>> dp;\n\tconst int buffer = 1;\n\tint dis(int a, int b) {\n\t\tif (a == -1 || b == -1) return
```\nclass Solution {\npublic:\n\tint n;\n\tvector<vector<vector<int>>> dp;\n\tconst int buffer = 1;\n\tint dis(int a, int b) {\n\t\tif (a == -1 || b == -1) return 0;\n\t\tint row1 = a / 6, row2 = b / 6;\n\t\tint col1 = a % 6, col2 = b % 6;\n\n\t\tint ans = (abs(row2 - row1) + abs(col2 - col1));\n\t\treturn ans;\n\t}\n\n\tint get(string &word, int start, int pos1, int pos2) {\n\t\tif (start >= n) return 0;\n\t\tint curr = word[start] - \'A\';\n\n\t\tint &ans = dp[start][pos1 + buffer][pos2 + buffer];\n\t\tif (ans != -1) return ans;\n\n\t\tint ans1 = dis(curr, pos1) + get(word, start + 1, word[start] - \'A\', pos2);\n\t\tint ans2 = dis(curr, pos2) + get(word, start + 1, pos1, word[start] - \'A\');\n\n\t\treturn ans = min(ans1, ans2);\n\t}\n\n\tint minimumDistance(string wordd) {\n\t\tn = wordd.size();\n\t\tdp.resize(n, vector<vector<int>>(30, vector<int>(30, -1)));\n\t\treturn get(wordd, 0, -1, -1);\n\t}\n};\n```\nI observed using an array instead of vector as DP, improved the runtime nearly 5 times.\n```\nclass Solution {\npublic:\n\tint n;\n\tint dp[302][27][27];\n\tconst int buffer = 1;\n\tint dis(int a, int b) {\n\t\tif (a == -1 || b == -1) return 0;\n\t\tint row1 = a / 6, row2 = b / 6;\n\t\tint col1 = a % 6, col2 = b % 6;\n\n\t\tint ans = (abs(row2 - row1) + abs(col2 - col1));\n\t\treturn ans;\n\t}\n\n\tint get(string &word, int start, int pos1, int pos2) {\n\t\tif (start >= n) return 0;\n\t\tint curr = word[start] - \'A\';\n\n\t\tint &ans = dp[start][pos1 + buffer][pos2 + buffer];\n\t\tif (ans != -1) return ans;\n\n\t\tint ans1 = dis(curr, pos1) + get(word, start + 1, word[start] - \'A\', pos2);\n\t\tint ans2 = dis(curr, pos2) + get(word, start + 1, pos1, word[start] - \'A\');\n\n\t\treturn ans = min(ans1, ans2);\n\t}\n\n\tint minimumDistance(string wordd) {\n        memset(dp,-1, sizeof(dp));\n\t\tn = wordd.size();\n\t\treturn get(wordd, 0, -1, -1);\n\t}\n};\n```
['Dynamic Programming', 'C', 'C++']