[Java] Dp solution for beginners like me with explanation
For such questions the initutions should be made based on the assumptions. We know that words and keyword have English Upper case letters. That being said this 
For such questions the initutions should be made based on the assumptions. We know that words and keyword have English Upper case letters. That being said this means position and distance between two letters can be calculated in 0(1) time while iterating over 26 letters.\n\nNow we are given that initail position of two fingers can be anything. That means to calculate the min val to type a word we have to consider all the possible position of two fingers i,j (complexitiy being 0(26^2)). This gives an idea that we have to recursion or DFS to check all possible cases.\n\nNow consider if my two fingers are at (i,j) and we have to type character at index k in the word. we either use finger at i or finger at j which gives us a minimum manhattan distance. This creates are recursive call. See code to see this part highlighted.\n\nNow see that if I move my finger to type that word I am at the new location of  fingers. There can be a case that from here I already did calculation to type rest of the letters in the word. This shows the overlapping subproblem condition hence dp is possible.\n\nlets define our dp\n\ndp[i][j][k]: Gives the min value to type letters after k index when fingers are at position i,j.\n\nThus dp[i][j][0] means min distance taken to type the whole word if I am at i,j initially.\n\nI also do some preprosses to make it easy to calculate manhattan distance without iterating the keyword.\n\n\n```\nclass Solution {\n    class Pair{\n        int x;\n        int y;\n        public Pair(int x, int y){\n            this.x = x;\n            this.y = y;\n        }\n    }\n    \n    Integer[][][] dp;\n    \n    public int manDis(int i,int j,HashMap<Integer,Pair> map){\n        return Math.abs(map.get(i).x -map.get(j).x) + Math.abs(map.get(i).y -map.get(j).y);\n    }\n    \n    public int helper(int i, int j, int index, String word, HashMap<Integer,Pair> map){\n        \n        if(index >= word.length())\n            return 0;\n        \n        if(dp[i][j][index] != null)\n            return dp[i][j][index];\n        \n        int newChar = word.charAt(index) - 65;\n        int i_cal = manDis(i,newChar,map);\n        int j_cal = manDis(j,newChar,map);\n\t\t// Recursive call\n        int val = Math.min(helper(newChar,j,index+1,word,map)+i_cal,\n                           helper(i,newChar,index+1,word,map)+j_cal);\n        dp[i][j][index] = val;\n        return dp[i][j][index];\n        \n    }\n    \n    public int minimumDistance(String word) {\n        \n\t\t// Preprocessed step\n        HashMap<Integer,Pair> map = new HashMap<>();\n        int count = 0;\n        for(int i=0;i<6;i++){\n            for(int j=0;j<6;j++){\n                if(count >= 26)\n                    break;\n                map.put(count,new Pair(i,j));\n                count++;\n            }\n        }\n        \n        dp = new Integer[26][26][301]; // defining dp\n        \n        int val=Integer.MAX_VALUE;\n        \n        for(int i=0;i<26;i++){\n            for(int j=0;j<26;j++){\n                val = Math.min(val,helper(i,j,0,word,map)); //Trying all possible fingers positions\n            }\n        }\n        \n        return val;\n    }\n}\n```\n\nComplexity is O(26*n*m)\n\nn = number of fingers \nm = length of the word
[]