我们时常用dp(动态规划)去解决某一些问题,但有没想过如果要你返回搜索路径,你该怎么做?
下面一题是用dp要求一份最小答案,我们返回最小答案那段路径,我们可以用在get_ans中查询路径是否和已存在dfs_cache中的dfs(i， j)进行比较,同时保留路径ans

class Solution:
    def findPermutation(self, nums: List[int]) -> List[int]:
        n = len(nums)
        @cache
        def dfs(i ,j):
            if i==(1<<n)-1:
                return abs(j - nums[0])
            res = inf
            for k in range(1, n):
                if i>>k&1:
                    continue
                res = min(dfs(i|1<<k, k)+abs(nums[k]-j), res)
            return res
        ans = []
        @cache
        def get_ans(i ,j)->None:
            ans.append(j)
            if i==(1<<n)-1:
                return
            res = dfs(i, j)
            for k in range(1, n):
                if i>>k&1:
                    continue
                if dfs(i|1<<k, k) + abs(nums[k]-j) == res:
                    get_ans(i|1<<k, k)
                    break
        get_ans(1, 0)
        return ans

最后，特别感谢 灵神 总结经验，让我能够分享我的学习和思考。