CPP | easy memoization | 5D DP with detail explaination
The states of the dp will be \n1. the current  index of the word : idx\n2. x and y positions of first finger\n3. x and y positions of the second finger\n\nNow w
The states of the dp will be \n1. the current  index of the word : idx\n2. x and y positions of first finger\n3. x and y positions of the second finger\n\nNow when we know this, the first move can be considered to be started by the first finger : //1\nFor the next moves, they can be using the first or the second finger. //2\nif(fing2r==6 && fing2c==6) represents that finger2 is being used for the first time. \nThe remaining task is to find the min distance! EZ!\n\n```\nclass Solution {\npublic:\n    \n    int getrow(char x){\n        int k=x-\'A\';\n        int row=k/6;\n        return row;\n    }\n    int getcol(char x){\n        int k=x-\'A\';\n        int col=k%6;\n        return col;\n    }\n    int dp[301][7][7][7][7];\n    int solve(string word, int idx, int fing1r, int fing1c, int fing2r, int fing2c){\n        if(idx==word.size()) return 0;\n        int dist=INT_MAX;\n        int r=getrow(word[idx]);\n        int c=getcol(word[idx]);\n        if(dp[idx][fing1r][fing1c][fing2r][fing2c]!=-1) return dp[idx][fing1r][fing1c][fing2r][fing2c];\n        if(idx==0) dist=min(dist,solve(word,1,r,c,fing2r,fing2c)); //1\n        else{ //2\n            int dist1=abs(r-fing1r)+abs(c-fing1c);\n            dist1+=solve(word,idx+1,r,c,fing2r,fing2c);\n            int dist2=abs(r-fing2r)+abs(c-fing2c);\n            if(fing2r==6 && fing2c==6) dist2=solve(word,idx+1,fing1r,fing1c,r,c);\n            else dist2+=solve(word,idx+1,fing1r,fing1c,r,c);\n            dist=min(dist1,dist2);\n        }\n        dp[idx][fing1r][fing1c][fing2r][fing2c] = dist;\n        return dist;\n    }\n    int minimumDistance(string word) {\n        memset(dp,-1,sizeof dp);\n        return solve(word,0,6,6,6,6);\n    \n```
['Dynamic Programming', 'C', 'C++']