Easy C++ Solution (Recursion + Memosiation) (Knapsack DP)
Intuition\nAt each step of the character of the string we can either type with finger 1 or type with finger 2. \n# Approach\npair p1 and p2 denote the last char
# Intuition\nAt each step of the character of the string we can either type with finger 1 or type with finger 2. \n# Approach\npair<int,int> p1 and p2 denote the last character coordinates of the first finger and last finger. Use them to find the minimum current distance using a hashmap (which maps the given table given in question with the coordinate pair {i,j}).\n\n\n\n# Code\n```\n#include <bits/stdc++.h>\nusing namespace std;\nclass Solution\n{\npublic:\n    int n;\n    map<char, pair<int, int>> mp;\n    typedef pair<int, int> pi;\n    map<pair<int, pair<pi, pi>>, int> dp;\n    int solve(string &s, int i, pair<int, int> p1, pair<int, int> p2)\n    {\n        if (i == n)\n            return 0;\n\n        if (dp.find({i, {p1, p2}}) != dp.end())\n            return dp[{i, {p1, p2}}];\n\n        int x = mp[s[i]].first, y = mp[s[i]].second;\n\n        int dist1 = abs(x - p1.first) + abs(y - p1.second);\n        if (p1.first == -1)\n            dist1 = 0;\n\n        int dist2 = abs(x - p2.first) + abs(y - p2.second);\n        if (p2.first == -1)\n            dist2 = 0;\n\n        dist1 += solve(s, i + 1, {x, y}, p2);\n        dist2 += solve(s, i + 1, p1, {x, y});\n\n        return dp[{i, {p1, p2}}] = min(dist1, dist2);\n    }\n    int minimumDistance(string word)\n    {\n        n = word.size();\n        char c = \'A\';\n        for (int i = 0; i < 4; i++)\n        {\n            for (int j = 0; j < 6; j++)\n                mp[c++] = {i, j};\n        }\n        mp[\'Y\'] = {4, 0}, mp[\'Z\'] = {4, 1};\n        return solve(word, 0, {-1, -1}, {-1, -1});\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']