[Python] DP using bfs() idea solution (Easy read) Similar idea with problem-1048
Explaination \n\nActually this is idea of solving this problem is more like a bfs() instead of dp. But we using a dict to record all possible optimized situatio
**Explaination **\n\nActually this is idea of solving this problem is more like a bfs() instead of dp. But we using a dict to record all possible optimized situation in the previous step(in dp this is called the previous status)\n\nThen we using previous status to build the next-step status, in the end choose the minimum distance sum from the last status\n\nPrev[left, right]  means previously which button left/right finger put on and what\'s the minimun result for that combination\n\n*Also to better understand this problem, there is a easier problem which is 1048 also using bfs() as the logic of dp.*\nhere is my explaination for 1048\nhttps://leetcode.com/problems/longest-string-chain/discuss/595686/Python-DP-with-bfs()-idea-6line\n\n```\nclass Solution:\n    def minimumDistance(self, W: str) -> int:\n        # build the board   0~26   x=6, y=5\n        chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"\n        B = collections.defaultdict(lambda:[])\n        for k in range(26):\n            (d, r) = divmod(k, 6)\n            B[chars[k]] = [d, r]\n        def get_dis(c1, c2, B):   #get distance\n            if not c1 or not c2: return 0   #if any of the finger not on any Button, we always can get the minimum result of 0\n            return abs(B[c1][0]-B[c2][0]) + abs(B[c1][1]-B[c2][1])\n\n        #dp  minimum distance at (left_position, right_position) and what is the char for each finger\n        prev, cur = collections.defaultdict(lambda:0), collections.defaultdict(lambda:math.inf)\n        prev[(None, None)] = 0  #None means put both finger no where\n        for w in W:\n            for (l, r) in prev: #continue update the dp like a bfs() so we build the next_stage of status base on what we have now\n                cur[(w, r)] = min(cur[(w, r)], prev[(l, r)] + get_dis(l, w, B))  #to merge all reapting result in same layer\n                cur[(l, w)] = min(cur[(a, w)], prev[(l, r)] + get_dis(r, w, B))\n            prev, cur = cur, collections.defaultdict(lambda:math.inf)\n\n        return min(prev.values())\n```
[]