Skip to content

3149. Find the Minimum Cost Array Permutation 👍

  • Time: $O(2^n \cdot n^2)$
  • Space: $O(2^n \cdot n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
 public:
  vector<int> findPermutation(vector<int>& nums) {
    const int n = nums.size();
    vector<vector<int>> mem(n, vector<int>(1 << n));
    // bestPick[last][mask] := the best pick, where `last` is the last chosen
    // number and `mask` is the bitmask of the chosen numbers
    vector<vector<int>> bestPick(n, vector<int>(1 << n));

    // Choose 0 as perm[0] since the score function is cyclic.
    getScore(nums, /*last=*/0, /*mask=*/1, bestPick, mem);
    return construct(bestPick);
  }

 private:
  // Returns the minimum score, where `last` is the last chosen number and
  // `mask` is the bitmask of the chosen numbers.
  int getScore(const vector<int>& nums, int last, unsigned mask,
               vector<vector<int>>& bestPick, vector<vector<int>>& mem) {
    if (popcount(mask) == nums.size())
      return abs(last - nums[0]);  // |perm[n - 1] - nums[perm[0]]|
    if (mem[last][mask] > 0)
      return mem[last][mask];

    int minScore = INT_MAX;
    for (int i = 1; i < nums.size(); ++i) {
      if (mask >> i & 1)
        continue;
      const int nextMinScore =
          abs(last - nums[i]) + getScore(nums, i, mask | 1 << i, bestPick, mem);
      if (nextMinScore < minScore) {
        minScore = nextMinScore;
        bestPick[last][mask] = i;
      }
    }

    return mem[last][mask] = minScore;
  }

  vector<int> construct(const vector<vector<int>>& bestPick) {
    vector<int> ans;
    int last = 0;
    int mask = 1;
    for (int i = 0; i < bestPick.size(); ++i) {
      ans.push_back(last);
      last = bestPick[last][mask];
      mask |= 1 << last;
    }
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
  public int[] findPermutation(int[] nums) {
    final int n = nums.length;
    int[][] mem = new int[n][1 << n];
    // bestPick[last][mask] := the best pick, where `last` is the last chosen
    // number and `mask` is the bitmask of the chosen numbers
    int[][] bestPick = new int[n][1 << n];

    // Choose 0 as perm[0] since the score function is cyclic.
    getScore(nums, /*last=*/0, /*mask=*/1, bestPick, mem);
    return construct(bestPick);
  }

  // Returns the minimum score, where `last` is the last chosen number and
  // `mask` is the bitmask of the chosen numbers.
  private int getScore(int[] nums, int last, int mask, int[][] bestPick, int[][] mem) {
    if (Integer.bitCount(mask) == nums.length)
      return Math.abs(last - nums[0]); // |perm[n - 1] - nums[perm[0]]|
    if (mem[last][mask] > 0)
      return mem[last][mask];

    int minScore = Integer.MAX_VALUE;
    for (int i = 1; i < nums.length; ++i) {
      if ((mask >> i & 1) == 1)
        continue;
      int nextMinScore = Math.abs(last - nums[i]) + getScore(nums, i, mask | 1 << i, bestPick, mem);
      if (nextMinScore < minScore) {
        minScore = nextMinScore;
        bestPick[last][mask] = i;
      }
    }

    return mem[last][mask] = minScore;
  }

  private int[] construct(int[][] bestPick) {
    int[] ans = new int[bestPick.length];
    int last = 0;
    int mask = 1;
    for (int i = 0; i < bestPick.length; ++i) {
      ans[i] = last;
      last = bestPick[last][mask];
      mask |= 1 << last;
    }
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
  def findPermutation(self, nums: list[int]) -> list[int]:
    n = len(nums)
    bestPick = [[0] * (1 << n) for _ in range(n)]

    @functools.lru_cache(None)
    def getScore(last: int, mask: int) -> int:
      if mask.bit_count() == len(nums):
        return abs(last - nums[0])

      minScore = math.inf
      for i in range(1, len(nums)):
        if mask >> i & 1:
          continue
        nextMinScore = abs(last - nums[i]) + getScore(i, mask | (1 << i))
        if nextMinScore < minScore:
          minScore = nextMinScore
          bestPick[last][mask] = i

      return minScore

    getScore(0, 1)
    return self._construct(bestPick)

  def _construct(self, bestPick: list[list[int]]) -> list[int]:
    ans = []
    last = 0
    mask = 1
    for _ in range(len(bestPick)):
      ans.append(last)
      last = bestPick[last][mask]
      mask |= 1 << last
    return ans