Python simple DFS with memoization with explanation
The intuition is pretty much the same as all the other DP ones in here. However I thought it might help people to see it in it\'s top-down format to understand 
The intuition is pretty much the same as all the other DP ones in here. However I thought it might help people to see it in it\'s top-down format to understand how we are getting to those tabular DP solutions.\nYou can simplify the problem to a normal min path question. At each step starting with the first letter in `word` we have two options, to type it using with one of our two fingers. Using each finger adds the cost equal to the distance of whatever that finger used to be on, and our new letter of the word. Which basically turns it into a simple min path recursion.\n\nWe also add -1 to our getDist() function as a special case. Basically considering it as a special character with 0 distance to all other chars.\n\n```\nfrom functools import lru_cache\n\nclass Solution:\n    def minimumDistance(self, word: str) -> int:\n        def getDist(a,b):\n            if a==-1 or b==-1: \n                return 0 # -1 means fingers are not on keys yet so their distance to everything is 0\n            else:\n                i = ord(a)-ord(\'a\')\n                j = ord(b)-ord(\'a\')\n                return abs(i//6-j//6) + abs(i%6-j%6)\n\n        # Just a simple dfs for finding the min path.\n        # We have 2 options at each point, to use the left or right finger to type the next word.\n        @lru_cache(maxsize=None)\n        def getMinDist(l,r,k):\n            if k == len(word):return 0\n            next = word[k].lower()\n            ret = min(getMinDist(next,r,k+1)+getDist(l,next), getMinDist(l,next,k+1)+getDist(r,next))\n            return ret\n            \n        return(getMinDist(-1,-1,0))
[]