十九 731. 毕业旅行问题 (状态压缩DP)

731. 毕业旅行问题 (状态压缩DP)

思路：使用状态压缩DP，dp[i][j]中i表示状态（二进制表示），j表示最后所在城市。算法时间复杂度是O(2^n*n2)，需要优化掉没有访问过1号城市的状态和无效状态。

import java.util.*;

public class Main {
    private static int n;
    private static int[][] w, dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        w = new int[n][n];
        dp = new int[1 << n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                w[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < (1 << n); i++) {
            Arrays.fill(dp[i], 0x3f);
        }
        
        dp[1][0] = 0;
        for (int k = 1; k < (1 << n); k += 2) {
            for (int i = 0; i < n; i++) {
                if ((k >> i & 1) == 0) { continue; }
                for (int j = 0; j < n; j++) {
                    if (((k - (1 << i)) >> j & 1) != 0) {
                        dp[k][i] = Math.min(dp[k][i], dp[k - (1 << i)][j] + w[j][i]);
                    }
                }
            }
        }
        
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            res = Math.min(res, dp[(1 << n) - 1][i] + w[i][0]);
        }
        
        System.out.println(res);
    }
}