状压DP

状压动态规划（Bitmask Dynamic Programming，状压DP）是一种优化技巧，通常用于解决组合优化问题，特别是集合的子集问题。以下是一个使用状压DP解决集合的最短路径问题的Java代码示例：

public class BitmaskDP {

    public static int shortestPath(int n, int[][] dist) {
        int totalStates = 1 << n;  // Total possible subsets

        int[][] dp = new int[n][totalStates];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp[0][1] = 0;  // Starting state: only the first city visited

        for (int mask = 1; mask < totalStates; mask++) {
            for (int u = 0; u < n; u++) {
                if ((mask & (1 << u)) != 0) {  // Check if u is in the current subset
                    for (int v = 0; v < n; v++) {
                        if (v != u && (mask & (1 << v)) != 0) {  // Check if v is in the current subset and not equal to u
                            dp[u][mask] = Math.min(dp[u][mask], dp[v][mask ^ (1 << u)] + dist[v][u]);
                        }
                    }
                }
            }
        }

        int minPath = Integer.MAX_VALUE;
        for (int u = 1; u < n; u++) {
            minPath = Math.min(minPath, dp[u][totalStates - 1] + dist[u][0]);
        }

        return minPath;
    }

    public static void main(String[] args) {
        int n = 4;  // Number of cities
        int[][] dist = {
            {0, 10, 15, 20},
            {10, 0, 35, 25},
            {15, 35, 0, 30},
            {20, 25, 30, 0}
        };

        int shortest = shortestPath(n, dist);
        System.out.println("Shortest Path: " + shortest);
    }
}

在这个示例中，shortestPath 方法使用状压DP解决了集合的最短路径问题。算法通过构建一个二维数组 dp 来保存状态转移，从而计算最短路径。

请注意，状压DP通常用于解决集合的子集问题，例如在TSP（Traveling Salesman Problem）中寻找最短路径。实际应用中，可能需要根据问题的需求进行适当的修改。