Python TSP,  straightforward DP by using Bellman-Held-Karp algorithm
Implement a straightforward Bellman\u2013Held\u2013Karp algorithm.\nIf we have A, B, C, D\nall the path contains 4 elements and ends with D can be written as:\n
Implement a straightforward Bellman\u2013Held\u2013Karp algorithm.\nIf we have A, B, C, D\nall the path contains 4 elements and ends with D can be written as:\n{A,B,C,D} ends with D\nIt can be generated from\n{A,B,C} ends with A + AD\n{A,B,C} ends with B + BD\n{A,B,C} ends with  C+ CD\nPick up the path which has the minimum length. This is the critical part of Bellman\u2013Held\u2013Karp algorithm.\nThen comes this solution. I am using (A, B, C) + (A, ) to encode {A,B,C} ends with A\n```python\nfrom functools import lru_cache\nclass Solution:\n    def shortestSuperstring(self, A: List[str]) -> str:\n        # TSP, DP \n        n = len(A)\n        w = [[0] * n for _ in range(n)]\n        for i in range(n):\n            for j in range(n):\n                for k in range(min(len(A[i]), len(A[j])), 0, -1):\n                    if A[j].startswith(A[i][-k:]):\n                        w[i][j] = k\n                        break\n        @lru_cache(None)\n        def dp(nodes):\n            if len(nodes) == 2:return A[nodes[0]]\n            end = nodes[-1]\n            end_idx = nodes.index(end) \n            # remove the current ending nodes from nodes[:-1]\n            nodes_wo_end = nodes[:end_idx]+nodes[end_idx+1:-1]\n            # A[end][w[node][end]:] will remove overlap part from the end node.\n            return min((dp(nodes_wo_end +(node, ))+A[end][w[node][end]:]\n                        for node in nodes_wo_end), key=len)\n        return min((dp(tuple(range(n))+(node, )) for node in range(n)), key=len)\n```\nDetail analysis is given here. \nhttps://medium.com/@jim.morris.shen/are-you-read-for-solving-the-traveling-salesman-problem-80e3c4ea45fc?source=friends_link&sk=b28ea8888460935401ae02f800d6ccd8\nPart of the code is using the reference here:\nhttps://leetcode.com/problems/find-the-shortest-superstring/discuss/195077/Clean-python-DP-with-explanations\n\nThanks.
[]