3D DP C++
\nclass Solution {\npublic:\n    map<char,pair<int,int>> mp;\n    int dp[303][37][37];\n    int dist(int i, string &word, pair<int,int> lastL, pair<int,int> las
```\nclass Solution {\npublic:\n    map<char,pair<int,int>> mp;\n    int dp[303][37][37];\n    int dist(int i, string &word, pair<int,int> lastL, pair<int,int> lastR){\n        if(i==word.size()){ return 0; }\n        int l=lastL.first*6+lastL.second, r=lastR.first*6+lastR.second;\n        if(dp[i][l][r]!=-1){ return dp[i][l][r]; }\n        int ans=INT_MAX;\n        int x=mp[word[i]].first, y=mp[word[i]].second;\n        int rD=(lastR.first==6)?0:abs(x-lastR.first)+abs(y-lastR.second);\n        int lD=(lastL.first==6)?0:abs(x-lastL.first)+abs(y-lastL.second);\n        ans=min(rD+dist(i+1,word,lastL,{x,y}),lD+dist(i+1,word,{x,y},lastR));\n        return dp[i][l][r]=ans;\n    }\n    int minimumDistance(string word) {\n        memset(dp,-1,sizeof(dp));\n        for(int i=0; i<26; i++){\n            mp[\'A\'+i]={i/6,i%6};\n        }\n        return dist(0,word,{6,0},{6,0});\n    }\n};\n```
['Dynamic Programming', 'C']