题解 | #旅行Ⅱ#

题意整理

给定N个城市，以及每个城市的开销。
一个前置城市数组，即去y城市之前必须先去x城市。
求牛妹用V元最多能去多少个城市旅游。

方法一（记忆化递归）

1.解题思路

前置知识：假设有N个城市，每个城市的编号是 $0，1，……N-1$ ，牛妹去了哪几个城市可以用一个N位二进制编码mask来表示，mask中对应位是1，则牛妹去了对应位编号的城市，mask中1的个数即是牛妹总共去的城市数。

递归如何推进：每一层递归有三个变量，V表示当前剩余花费，mask表示当前二进制编码，cityNum表示当前最多可去的城市数目。每次尝试从N个城市中选一个城市，如果该城市没有去过，并且其前置城市都去过了，就可以去这个城市，然后V减去当前城市开销，mask或上当前城市编号所在二进制位，cityNum加一。在每层递归中，计算cityNum的最大值。
每一层递归返回什么：返回当前层的最大可去城市数目。

由于普通递归会有很多重复的计算，所以用一个记忆数组来记录每一层的返回值。

动图展示：
图片说明

2.代码实现

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整型
     */
    //记忆数组
    int[] memo;
    //前置城市限制数组
    int[][] limit;
    //城市数目
    int N;
    //旅游花费
    int V;
    //城市开销数组
    int[] A;
    //最大可去城市数目
    int max;
    public int Travel (int N, int V, int[] A, Point[] List) {
        //初始化记忆数组、前置数组、城市数、花费、开销数组、最大可去城市数
        memo=new int[1<<N];
        limit=new int[N][N];
        for(Point p:List){
            limit[p.y-1][p.x-1]=1;
        }
        this.N=N;
        this.A=A;
        this.V=V;
        this.max=0;
        return dfs(V,0,0);
    }

    public int dfs(int V,int mask,int cityNum){
        //如果记忆数组中有值，直接返回
        if(memo[mask]!=0){
            return memo[mask];
        }
        //求可去最大城市数目
        max=Math.max(max,cityNum);
        memo[mask]=max;
        for(int i=0;i<N;i++){
            //如果i城市已经去过，或者花费不够了，直接跳过
            if (((mask>>i)&1)!=0||V<A[i]) continue;
            boolean pass=true;
            for(int j=0;j<N;j++){
                if(limit[i][j]==1&&((mask>>j)&1)==0){
                    pass=false;
                    break;
                }
            }
            //如果前置城市都去过了，直接递归去i城市
            if(pass){
                dfs(V-A[i],mask|(1<<i),cityNum+1);
            }
        }
        return max;
    }
}

3.复杂度分析

时间复杂度：由于每个城市要么去，要么不去，总共有 $2^n$ 种mask位，所以递归的层数是 $2^n$ ，而每个城市都要检查自身的前置城市是否访问完毕，需要 $O(n^2)$ 的时间复杂度，所以总的时间复杂度是 $O(n^2*2^n)$ 。
空间复杂度：需要额外大小为 $2^n$ 的记忆数组，所以空间复杂度是 $O(2^n)$ 。

方法二（状压dp）

1.解题思路

状态定义： $dp[i]$ 表示二进制mask为i时，需要的旅游开销。
状态初始化：将mask为0设为起点，表示不去任何城市时，旅游开销是0。其他mask位设为无穷大，表示不可达。
状态转移：如果当前城市没有来过，并且当前城市i的前置城市都去过了，则可转移到下一个mask位，对应开销加上当前城市开销，即 $dp[mask|1<<i]=dp[mask]+A[i]$ 。

当所有的mask位都统计完成后，计算满足开销不大于V的最大可去城市数目（mask位中1的个数）。

2.代码实现

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) {
        //初始化限制数组
        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;
    }
}

3.复杂度分析

时间复杂度：总共三层循环，第一层大小 $2^n$ ，第二层和第三层大小都是n，所以时间复杂度是 $O(n^2*2^n)$ 。
空间复杂度：需要额外大小为 $2^n$ 的状压dp数组，所以空间复杂度是 $O(2^n)$ 。