最短 Hamilton 路径

NP Hard 问题，暴力时间复杂度 $O (n*n!)$

这题正解其实是利用状压 DP 的方法来做，状态转移方程为

dp[i][j] = min{dp[i][j], dp[i - (1 << j)][k] + map[k][j]}

其中 map 数组为权值，map [k][j] 是点 k 到点 j 的权值

dp [i][j] 表示当前已经走过点的集合为 i，移动到 j。所以这个状态转移方程就是找一个中间点 k，将已经走过点的集合 i 中去除掉 j（表示 j 不在经过的点的集合中），然后再加上从 k 到 j 的权值

问题在于如何表达已经走过点的集合 i，其实很简单，假如走过 0,1,4 这三个点，我们用二进制 10011 就可以表示，2,3 没走过所以是 0

那么走过点的集合 i 中去除掉点 j 也很容易表示 i - (1 << j)，比方说 i 是 {0,1,4}，j 是 1，那么 i = 10011，(1 << j) = 10，i - (1 << j) = 10001

那么问题的答案就应该是 dp [01....111][n-1]，表示 0~n-1 都走过，且当前移动到 n-1 这个点

分析一下时间复杂度，n 为 20 的时候，外层循环 (1<<20)，内层循环 20，所以整体时间复杂度 $O (20*2^{20})$，这比 $O (n*n!)$ 快多了

import java.util.Scanner;

public class Main {
    static int[][] dp = new int[1 << 20][20];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                map[i][j] = cin.nextInt();
        for (int i = 0; i < (1 << n); i++) 
            for (int j = 0; j < n; j++)
                dp[i][j] = Integer.MAX_VALUE >> 1;
        dp[1][0] = 0;
        for (int i = 0; i < (1 << n); i++) // 二进制枚举走过的点的集合
            for(int j = 0; j < n; j++)
                if ((i >> j & 1) == 1)
                    for (int k = 0; k < n; k++) 
                        if ((i - (1 << j) >> k & 1) == 1)
                            dp[i][j] = Math.min(dp[i][j], dp[i - (1 << j)][k] + map[j][k]);
        System.out.println(dp[(1 << n) - 1][n - 1]);
    }
}