[Python3] dp
Please pull this commit for solutions of weekly 414. \n\n\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n      
Please pull this [commit](https://github.com/gaosanyong/leetcode/commit/49eb160eaf0d0c3b6bb97edea0f15ad8feb660b5) for solutions of weekly 414. \n\n```\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        n = len(positions)\n        dist = [[0]*n for _ in range(n+1)]\n        positions.append([kx, ky])\n        for i in range(n+1): \n            for j in range(n): \n                if i != j: \n                    queue = deque([positions[i]])\n                    seen = set()\n                    step = 0 \n                    while queue: \n                        for _ in range(len(queue)): \n                            x, y = queue.popleft()\n                            if [x, y] == positions[j]: \n                                dist[i][j] = step  \n                                break \n                            for xx, yy in (x-2, y-1), (x-2, y+1), (x-1, y-2), (x-1, y+2), (x+1, y-2), (x+1, y+2), (x+2, y-1), (x+2, y+1): \n                                if 0 <= xx < 50 and 0 <= yy < 50 and (xx, yy) not in seen: \n                                    queue.append([xx, yy])\n                                    seen.add((xx, yy))\n                        else: \n                            step += 1\n                            continue \n                        break \n\n        ops = [max, min]\n        init = [0, inf]\n        \n        @cache\n        def fn(i, m, turn): \n            if m == (1<<n) - 1: return 0 \n            ans = init[turn]\n            for k in range(n): \n                if not m & 1<< k: \n                    mm = m ^ 1<<k \n                    ans = ops[turn](ans, dist[i][k] + fn(k, mm, turn^1))\n            return ans \n        \n        return fn(n, 0, 0)\n```
['Python3']