# 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: 解題步驟
- 將題目簡略畫成圖，如下所示
- 發現到所求和 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，要繼續往上推的話，也就是走到其他城市，如下所示

        for ( int i = 0; i < n; ++i) {
            if (bit & (1<<i)) {
                // 代表尚未走過
            }
        }

- 每個index值跟所求結果進行列舉，以尋找關係

## :pencil2: 程式碼
### 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;
    }
}