Easy to Understand 3D DP Solution
Order to Proceed:\n1. Place finger1 at index 0 always.\n2. finger2 can be placed at anywhere from len = 1 to n-1\n3. Now calculate all permutations for the fing
**Order to Proceed:**\n1. Place finger1 at index 0 always.\n2. finger2 can be placed at anywhere from len = 1 to n-1\n3. Now calculate all permutations for the finger1 and finger2 for each character\n4. Memoize the solution using 3D dp(```dp[pair1][pair2][index]```) .To simplify I have converted pair1 to ```[x1][y1] ```and pair2 to ```[x2][y2]``` to a 5D dp which is essentially 3D.\n5. The minimum cost amongst these is the answer.\n```\nclass Solution {\npublic:\n    map<char,pair<int,int>> mp;\n    int dp[7][7][7][7][301];\n    int dfs(string word, pair<int,int> finger1, pair<int,int> finger2, int currIndex,int len){\n        if(currIndex == len){\n            return 0;\n        }\n        // cout << currIndex << endl;\n        int x1 = finger1.first;\n        int x2 = finger2.first;\n        int y1 = finger1.second;\n        int y2 = finger2.second;\n        if(dp[x1][y1][x2][y2][currIndex] != -1){\n            return dp[x1][y1][x2][y2][currIndex];\n        }\n        pair<int,int> curr_p = mp[word[currIndex]];\n        int curr_x = curr_p.first;\n        int curr_y = curr_p.second;\n        int dist1 = abs(x1-curr_x) + abs(y1-curr_y);\n        int dist2 = abs(x2-curr_x) + abs(y2-curr_y);\n        return dp[x1][y1][x2][y2][currIndex] = min(dist1 + dfs(word,curr_p,finger2,currIndex+1,len), \n                   dist2 + dfs(word,finger1,curr_p,currIndex+1,len));\n    }\n    int minimumDistance(string word) {\n        int len = word.length();\n        char ch = \'A\';\n        for(int i=0;i<5;i++){\n            for(int j=0;j<6;j++){\n                mp[ch] = make_pair(i,j);\n                ch++;\n                if(i==4 && j==2){\n                    break;\n                }\n            }\n        }\n        for(int i=0;i<7;i++){\n            for(int j=0;j<7;j++){\n                for(int k=0;k<7;k++){\n                    for(int l=0;l<7;l++){\n                        for(int m=0;m<301;m++){\n                            dp[i][j][k][l][m] = -1;\n                        }\n                    }\n                }\n            }\n        }\n        pair<int,int> finger1 = make_pair(1,1);\n        pair<int,int> finger2 = make_pair(0,0);\n        char firstChar = word[0];\n        finger1 = mp[firstChar];\n        int minCost = INT_MAX;\n        for(int j=1;j<len;j++){\n            finger2 = mp[word[j]];\n            minCost = min(minCost,dfs(word,finger1,finger2,0,len));\n        }\n        return minCost == INT_MAX? 0: minCost;\n    }\n};\n```
['Dynamic Programming', 'C++']