---
# System prepended metadata

title: 3149. Find the Minimum Cost Array Permutation
tags: [LeetCode -Hard]

---

# 3149. Find the Minimum Cost Array Permutation

> ***View the book with <i class="fa fa-book"></i> Book Mode.***

- [**LeetCode筆記目錄**](https://hackmd.io/@WeiYee/SyABdj_eA)

## :book: 題目

**網址:**  https://leetcode.com/problems/find-the-minimum-cost-array-permutation/description/

## :dart: 解題步驟
- 將題目簡略畫成圖，如下所示
![解題](https://hackmd.io/_uploads/ryknlqYVC.png)
- 發現到所求和 Travelling salesman problem 有關，只是所求為最短路徑的順序。另外此題的最短路徑，不會因為起點而受影響，因此 0 ~ n 都可以，但是題目要求 lexicographically smallest，所以可知起點必定為 0。
- Travelling salesman problem: 總共有 n 個城市 (0  ~  n) ，且初始點為0，訪問每座城市一次並回到起始城市的最短距離<br><br>
    - 找 0、1、2，因為以下路徑，剩下要遍歷的城市都相同，所以取最小
        ``` 
          |0 ⭢ 1| + |1 ⭢ 2|
          |0 ⭢ 2| + |2 ⭢ 1|
        ```
    - 找 0、1、2、3，因為以下路徑，剩下要遍歷的城市都相同，所以取最小
        ``` 
          dp(0、1、2) + |prev ⭢ 3|
          dp(0、1、3) + |prev ⭢ 2|
          dp(0、2、3) + |prev ⭢ 1|
        ```
    - 假設目前求遍歷 城市 0 ~ k 的最小距離，且初始點為0，即以下取最小
        ``` 
          dp(0、1、2、...、k-2、k-1) + |prev ⭢ k  |
          dp(0、1、2、...、k-2、k)   + |prev ⭢ k-1|
          ...
          dp(0、2、3、...、k-1、k)   + |prev ⭢ 1  |
        ```
- 使用 **dp + bitset** 求值
    - 建表，1:已走過，0:尚未經過，n 個城市總共需要 $2^n$個<br><br>
      | index | value |  description   |
      |:-----:|:-----:|:--------------:|
      | **0** |  000  |       0        |
      | **1** |  001  |     0 ⭢ 1      |
      | **2** |  010  |     0 ⭢ 2      |
      | **3** |  011  |  dp(0、1、2)   |
      | **4** |  100  |     0 ⭢ 3      |
      | **5** |  101  |  dp(0、1、3)   |
      | **6** |  110  |  dp(0、2、3)   |
      | **7** |  111  | dp(0、1、2、3) |
      |  ...  |  ...  |      ...       |
    - 當 bit 目前為 $2^n-1$ ( **n-1 個 1**) 代表已經遍歷完所有城市
    - 另外 像今天如果是 0101，要繼續往上推的話，也就是走到其他城市，如下所示
      ``` java = 
        for ( int i = 0; i < n; ++i) {
            if (bit & (1<<i)) {
                // 代表尚未走過
            }
        }
      ``` 
- 每個index值跟所求結果進行列舉，以尋找關係

## :pencil2: 程式碼
### Java
```java=
class Solution {
    int[][] tspDistance, tspNextPoint;

    public int[] findPermutation(int[] nums) {
        int n = nums.length;
        tspDistance = new int[1 << n][n];
        tspNextPoint = new int[1 << n][n];
        tsp(1, 0, nums);
        int[] res = new int[n];
        for (int i = 1, mask = 1, prev = 0; i < n; ++i) {
            res[i] = tspNextPoint[mask][prev];
            prev = res[i];
            mask = mask | (1 << prev);
        }
        return res;
    }

    private int tsp(int mask, int prev, int[] nums) {
        int n = nums.length;
        if (mask == (1 << n) - 1) return Math.abs(prev - nums[0]);
        if (tspDistance[mask][prev] != 0) return tspDistance[mask][prev];

        int minDistance = 200, nextPoint = 0;
        for (int next = 0, addMask = 1; next < n; ++next) {
            if ((mask & addMask) == 0) {
                int res = tsp(mask | addMask, next, nums) + Math.abs(prev - nums[next]);
                if (minDistance > res) {
                    minDistance = res;
                    nextPoint = next;
                }
            }
            addMask <<= 1;
        }
        tspNextPoint[mask][prev] = nextPoint;
        return tspDistance[mask][prev] = minDistance;
    }
}
```