毕业旅行问题

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int res;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[][] matrix = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = in.nextInt();
                }
            }
            long res = getShortestWay(n, matrix);
            System.out.println(res);
        }
    }
    static long getShortestWay (int n, int[][] matrix) {
        boolean[] visited = new boolean[n]; Arrays.fill(visited, false);
        int state_num = (1<<n) - 1; // 途径 1 -> n-1 
        long[][] dp = new long[n][state_num+1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i],  Integer.MAX_VALUE/2);
        }
        Set<Integer> set = new HashSet<>();

        for (int i = 1; i < n; i++) {
            set.add(1<<i);
            dp[i][1<<i] = matrix[0][i];
        }

        int endState = (1<<n)-2;
        while (!set.isEmpty()) {
            Set<Integer> newSet = new HashSet<>();
            for (int ss:set) {
                if (ss == endState) continue;
                // 当前状态 是 ss
                for (int i = 1; i < n; i++) {
                    // if (dp[i][ss] == Integer.MAX_VALUE/2) {
                    //     continue;
                    // }
                    for (int j = 1; j < n; j++) {
                        if (((1<<j) & ss) != 0 ) continue; // 如果已经访问过， 则取消
                        int newState = ss | (1<<j);
                        dp[j][newState] = Math.min(dp[j][newState], 
                                          dp[i][ss] + matrix[i][j]);
                        newSet.add(newState);
                    }
                }
            }
            set = newSet;
        }
        long res = Integer.MAX_VALUE/2;
        for (int i = 1; i < n; i++) {
            res = Math.min(res, dp[i][endState] + matrix[i][0]);
        }
        return res;   
    }
}

import java.util.*;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] nums = new int[N][N];
        for(int i=0; i < N; i++){
            for(int j=0; j < N; j++){
                nums[i][j] = sc.nextInt();
            }
        }
        Integer[][] memo = new Integer[(1<<N)][N];
        System.out.println(DFS(nums, 0, 0, memo));
    }
    
    private static int DFS(int[][] nums, int idx, int state, Integer[][] memo){
        int n = nums.length;
        if(state == (1<<n)-2){ //防止出现0-1-2-0-3的情况
            return nums[idx][0];
        }
        if(memo[state][idx] != null) return memo[state][idx];
        int ret = Integer.MAX_VALUE;
        for(int i=1; i < n; i++){
            if((state & (1<<i)) != 0) continue;
            ret = Math.min(ret, nums[i][idx] + DFS(nums, i, (state ^ (1<<i)), memo));
        }
        memo[state][idx] = ret;
        return ret;
    }
    
}

import java.util.*;
public class Main {
    //备忘录
    public static int[][] memo;
    //自上而下的dp函数
    public static int dp(int city, int j, int[][] dist) {
        //中止条件
        if(j == 0)
            return dist[city][0];
        //如果命中，直接返回
        if(memo[city][j] != -1)
            return memo[city][j];
        int ans = Integer.MAX_VALUE;
        for(int i = 1; i < dist.length; i++) {
            if(((j >> (i-1)) & 1) == 1) {
                j ^= (1 << (i-1));
                //记录这一轮的最小答案
                ans = Math.min(ans, dist[city][i]+dp(i, j, dist));
                j ^= (1 << (i-1));
            }
        }
        //添加至备忘录
        memo[city][j] = ans;
        return ans;
    }
    
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int cityNum = in.nextInt();// 城市数目
        int[][] dist = new int[cityNum][cityNum];
        for (int i = 0; i < dist.length; i++) {
            for (int j = 0; j < cityNum; j++) {
                dist[i][j] = in.nextInt();
            }
        }
        //对1进行左移n-1位，值刚好等于2^(n-1)
        int V = 1 << (cityNum - 1);
        memo = new int[cityNum][V];
        //初始化memo备忘录
        for (int i = 0; i < cityNum; i++) {
            for(int j = 0; j < V; j++) {
                memo[i][j] = -1;
            }
        }
        int ans = dp(0 , V-1, dist);
        System.out.println(ans);
    }
}