func findPermutation(a []int) []int {
n := len(a)
u := 1<<n - 1
f := make([][]int, 1<<n)
g := make([][]int, 1<<n)
for i := range f {
f[i] = make([]int, n)
for j := range f[i] {
f[i][j] = math.MaxInt
}
g[i] = make([]int, n)
}
for j := range f[u] {
f[u][j] = abs(j - a[0])
g[u][j] = -1
}
for s := u - 2; s > 0; s -= 2 { // 注意偶数不含 0，是无效状态
for j := 0; j < n; j++ {
if s>>j&1 == 0 { // 无效状态，因为 j 一定在 s 中
continue
}
for k := 1; k < n; k++ {
if s>>k&1 > 0 { // k 之前填过
continue
}
v := f[s|1<<k][k] + abs(j-a[k])
if v < f[s][j] {
f[s][j] = v
g[s][j] = k // 记录该状态下填了哪个数
}
}
}
}
ans := make([]int, 0, n)
for s, j := 0, 0; j >= 0; {
ans = append(ans, j)
s |= 1 << j
j = g[s][j]
}
return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
class Solution {
public int[] findPermutation(int[] a) {
int n = a.length;
int[][] memo = new int[1 << n][n];
for (int[] row : memo) {
Arrays.fill(row, -1); // -1 表示没有计算过
}
int[] ans = new int[n];
makeAns(1, 0, a, memo, ans, 0);
return ans;
}
private int dfs(int s, int j, int[] a, int[][] memo) {
if (s == (1 << a.length) - 1) {
return Math.abs(j - a[0]);
}
if (memo[s][j] != -1) { // 之前计算过
return memo[s][j];
}
int res = Integer.MAX_VALUE;
for (int k = 1; k < a.length; k++) {
if ((s >> k & 1) == 0) { // k 之前没填过
res = Math.min(res, dfs(s | 1 << k, k, a, memo) + Math.abs(j - a[k]));
}
}
memo[s][j] = res; // 记忆化
return res;
}
private void makeAns(int s, int j, int[] a, int[][] memo, int[] ans, int i) {
ans[i] = j;
if (s == (1 << a.length) - 1) {
return;
}
int finalRes = dfs(s, j, a, memo);
for (int k = 1; k < a.length; k++) {
if ((s >> k & 1) == 0 && dfs(s | 1 << k, k, a, memo) + Math.abs(j - a[k]) == finalRes) {
makeAns(s | 1 << k, k, a, memo, ans, i + 1);
break;
}
}
}
}
class Solution:
def findPermutation(self, a: List[int]) -> List[int]:
n = len(a)
@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(s: int, j: int) -> int:
if s == (1 << n) - 1:
# 所有位置都填完了，最后一个位置是下标 j
return abs(j - a[0])
res = inf
# 枚举当前位置填下标 k
for k in range(1, n):
if s >> k & 1 == 0: # k 之前没填过
res = min(res, dfs(s | 1 << k, k) + abs(j - a[k]))
return res
ans = []
# 原理见上面贴的题解链接
def make_ans(s: int, j: int) -> None:
ans.append(j)
if s == (1 << n) - 1:
return
final_res = dfs(s, j)
for k in range(1, n):
if s >> k & 1 == 0 and dfs(s | 1 << k, k) + abs(j - a[k]) == final_res:
make_ans(s | 1 << k, k)
break
make_ans(1, 0)
return ans
# 递推
def findPermutation2(self, a: List[int]) -> List[int]:
n = len(a)
f = [[inf] * n for _ in range(1 << n)]
g = [[-1] * n for _ in range(1 << n)]
for j in range(n):
f[-1][j] = abs(j - a[0])
for s in range((1 << n) - 3, 0, -2): # 注意偶数不含 0，是无效状态
for j in range(n):
if s >> j & 1 == 0: # 无效状态，因为 j 一定在 s 中
continue
for k in range(1, n):
if s >> k & 1: # k 之前填过
continue
v = f[s | 1 << k][k] + abs(j - a[k])
if v < f[s][j]:
f[s][j] = v
g[s][j] = k # 记录该状态下填了哪个数
ans = []
s = j = 0
while j >= 0:
ans.append(j)
s |= 1 << j
j = g[s][j]
return ans
