最短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]);
    }
}