[Python] simple DP with explanation (270 ms beats 100%)
Base case: When there is only 1 character to type, we only use 1 finger.\n\nFor new case n, we expand each case n-1 with 2 possibilities\n type the new characte
**Base case**: When there is only 1 character to type, we only use 1 finger.\n\nFor **new case n**, we expand each case n-1 with 2 possibilities\n* type the new character using finger 1\n* type the new character using finger 2\n\t* if finger 2 is free, no additional distance is added\n\n\n**We can further improve the performance**\n* there are only 26 possible finger positions.\n* there are only 26*26 different combinations of finger movements\n\n```\nfrom functools import lru_cache\nclass Solution:\n    def minimumDistance(self, A):\n        \n        @lru_cache(maxsize=None)\n        def get_distance(current_pos, next_pos):\n            if current_pos == -1: return 0\n            return abs(current_pos // 6 - next_pos // 6) + abs(current_pos % 6 - next_pos % 6)\n        \n        @lru_cache(maxsize=None)\n        def to_num(c):\n            return ord(c) - ord(\'A\')\n\n        # key: (i,j) i is the position of the first finger, j is the positino of the second finger\n        dp = {(to_num(A[0]), -1): 0} # base case, -1 means the second finger is free\n        for n in [to_num(c) for c in A[1:]]:\n            new_dp = {}\n            for (f1, f2), d in dp.items():\n                new_dp[n, f2] = min(new_dp.get((n, f2), math.inf), d + get_distance(f1, n))\n                new_dp[f1, n] = min(new_dp.get((f1, n), math.inf), d + get_distance(f2, n))\n            dp = new_dp\n            \n        return min(dp.values())\n\t\t# AC: 270 ms\n```\n
['Dynamic Programming', 'Memoization', 'Python']