题解 | #旅行Ⅱ#

算法思想一：递归+记忆化递归

解题思路：

可以对 $2^n$ 种状态利用二进制掩码形式逐一对其递归进行搜索，每次查看经费和前后续关系。搜索函数中 $m$ 为当前的状态数， $n$ 为当前最大这段序列可访问的最大城市数，递归的时候减小经费 $V$ ，改变 $m$ 与 $n$ 即可进入子问题。为了防止递归处理的问题太大，可以用数组dp记录所有的前面计算过的序列的可访问的最大值。

图解：

代码展示：

C++版本

/**
 * struct Point {
 *    int x;
 *    int y;
 *    Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param N int整型 N
     * @param V int整型 V
     * @param A int整型vector A
     * @param List Point类vector List
     * @return int整型
     */
    int search(vector<vector<int> >& city, vector<int>& dp, vector<int>& A, int N, int V, int m, int n){
        if(dp[m] != 0)
            return dp[m];
        int maxn = n;
        for(int i = 0; i < N; i++){
            if(((1  0 || A[i] > V)  // 如果当前 节点已经走过或者费用不足，就不需要进行搜索
                continue;
            bool flag = true;
            for(int j = 0; j < city[i].size(); j++){ //查看它的前驱节点是否走过
                if(((1 << city[i][j]) & m) == 0){
                    flag = false;
                    break;
                }
            }
            if(flag) //找到最大值
                maxn = max(maxn, search(city, dp, A, N, V-A[i], m ^ (1 << i), n + 1));
        }
        dp[m] = maxn;  //记忆避免多次递归
        return dp[m];
    }
    int Travel(int N, int V, vector<int>& A, vector<Point>& List) {
        // write code here
        vector dp(1 << N, 0); //一共2^N个状态
        vector > city(N, vector()); //记录城市的先后顺序
        for(int i = 0; i < List.size(); i++)
            city[List[i].y - 1].push_back(List[i].x - 1);
        return search(city, dp, A, N, V, 0, 0);
    }
};

复杂度分析

时间复杂度 $O(2^n*n^2)$ ：递归中需要循环的部分其实只有dp的大小，其他的都是直接返回

空间复杂度 $O(2^n+n^2)$ ：dp占用空间 $O(2^n)$ ，city最差情况下 $O(n^2)$

算法思想二：状压dp

解题思路：

解题思路
1、状态定义：dp[i]表示二进制mask为i时，需要的旅游开销。
2、状态初始化：将mask为0设为起点，表示不去任何城市时，旅游开销是0。其他mask位设为无穷大，表示不可达。
3、状态转移：如果当前城市没有来过，并且当前城市i的前置城市都去过了，则可转移到下一个mask位，对应开销加上当前城市开销，即 $dp[mask|1<<i]=dp[mask]+A[i]$ 。
当所有的mask位都统计完成后，计算满足开销不大于V的最大可去城市数目（mask位中1的个数）。

代码展示：

JAVA版本

import java.util.*;
/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param N int整型 N
     * @param V int整型 V
     * @param A int整型一维数组 A
     * @param List Point类一维数组 List
     * @return int整型
     */
    public int Travel (int N, int V, int[] A, Point[] List) {
        // write code here
        //初始化限制数组
        int[][] limit=new int[N][N];
        for(Point p:List){
            limit[p.y-1][p.x-1]=1;
        }
        //初始化状态压缩dp，dp[i]表示二进制mask为i时，需要的旅游开销
        int[] dp=new int[1<<N];
        Arrays.fill(dp,Integer.MAX_VALUE/2);
        dp[0]=0;
        for(int mask=0;mask<(1<<N);mask++){
            //如果mask不可达，直接跳过
            if(dp[mask]==Integer.MAX_VALUE/2) continue;
            for(int i=0;i<N;i++){
                //如果当前城市已经来过，则跳过
                if(((mask>>i)&1)!=0) continue;
                //判断当前城市i是否还有未去过的前置城市
                boolean pass=true;
                for(int j=0;j<N;j++){
                    if(limit[i][j]==1&&((mask>>j)&1)==0){
                        pass=false;
                        break;
                    }
                }
                if(!pass) continue;
                //如果前置城市都去过了，则跳到下一个mask
                dp[mask|1<<i]=dp[mask]+A[i];
            }
        }

        int res=0;
        for(int mask=0;mask<(1<<N);mask++){
            //如果旅游开销不大于V，则计算对应的最大的可去城市数
            if(dp[mask]<=V){
                res=Math.max(res,Integer.bitCount(mask));
            }
        }
        return res;
    }
}

复杂度分析

时间复杂度 $O(2^n*n^2)$ ：总共三层循环，第一层大小2^n，第二层和第三层大小都是n

空间复杂度 $O(2^n)$ ：dp占用空间 $O(2^n)$