LC 100312. 找出分数最低的排列
https://leetcode.cn/problems/find-the-minimum-cost-array-permutation/description/
这题看了提示才知道的，很有效的一点是这个score function是循环的，所以肯定是0开头的。然后这个问题其实是一个TSP问题，可以用动态规划来有效求解。
这个动态规划的状态数量是在 \(O(n * 2^n)\) , 时间复杂度这个我不知道怎么分析，比 \(O(n^2 * 2^n)\) 这个应该更低，所以对于 n<=14 来说应该是很有效的。
class Solution:
def findPermutation(self, nums: List[int]) -> List[int]:
n = len(nums)
import functools
@functools.cache
def dfs(last, mask):
if mask == ((1 << n) - 1):
return abs(last - nums[0]), [last]
from math import inf
ans = inf
perm = None
for j in range(n):
if mask & (1 << j) == 0:
c = abs(last - nums[j])
r, p = dfs(j, mask | (1 << j))
c += r
if c > ans: continue
if c < ans or (perm is None or perm > p):
perm = p
ans = c
return ans, [last] + perm
ans, perm = dfs(0, 1)
return perm