题解 | #旅行Ⅱ#

题目描述
牛妹出去旅行啦，她准备去N个城市旅行，去每个城市的开销是Ai元。但是牛妹有强迫症，她想在去y城市之前先旅游x城市，于是牛妹列出了这些限制条件List。并且牛妹很节约，她只有V元，她想知道她最多能到多少个城市去旅游。

方法一：递归法

求解思路
对于求解本题目，我们首先将牛妹去过的城市用一个二进制数组存储下来，其中0表示没去过该城市，1表示去过该城市。同时我们设置三个变量，V表示当前剩余花费，mask表示当前二进制编码，cityNum表示当前城市的数目。对于递归，我们每次从N个城市中选一个城市，如果该城市没有去过，当且其前置城市都去过了，那么就可以去这个城市，然后用V减去当前城市的开销，并且更新mask和cityNum，递归上述操作，最终求得最大可去城市数目。

图片说明

解题代码

import java.util.*;
public class Solution {
    int[] memory; // 记忆数组
    int[][] limit; // 前置城市限制数组
    int N; // 城市数目
    int V; // 旅游花费
    int[] A; // 城市开销数组
    int mymax; // 最大可去城市数目
    public int Travel (int N, int V, int[] A, Point[] List)
    {
        memory=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.mymax=0;
        return dfs(V,0,0);
    }
    public int dfs(int V,int mask,int cityNum){
        if(memory[mask]!=0)
        {
            return memory[mask]; // 如果记忆数组中有值，直接返回
        }
        mymax=Math.max(mymax,cityNum); // 求可去最大城市数目
        memory[mask]=mymax;
        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 mymax; // 返回结果即可
    }
}

复杂度分析
时间复杂度：两层循环嵌套mask二进制数组的递归，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：使用二进制数组来记录城市是否被访问，因此空间复杂度为 $O$ ( $图片说明$ )

方法二：优化dp解法

求解思路
对于本问题求解，我们也可以使用dp的思路进行求解，我们定义dp[i]为旅游所需要的开销。如果当前城市没有来过，并且当前城市的前置城市都去过了，则对二进制数组进行更新，并且对应的花费和城市数目进行更新，因此我们有dp[mask|1<<i] = dp[mask]+A[i].最后按照上述思路，即可得到本题的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    public int Travel (int N, int V, int[] A, Point[] List)
    {
        int[][] mylimit=new int[N][N]; // 初始化限制数组
        for(Point p:List)
        {
            mylimit[p.y-1][p.x-1]=1;
        }
        int[] mydp=new int[1<<N]; // 初始化状态压缩dp，dp[i]表示二进制mask为i时，需要的旅游开销
        Arrays.fill(mydp,Integer.MAX_VALUE/2);
        mydp[0]=0;
        for(int mask=0;mask<(1<<N);mask++)
        {   //如果mask不可达，直接跳过
            if(mydp[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(mylimit[i][j]==1&&((mask>>j)&1)==0)
                    {
                        pass=false;
                        break;
                    }
                }
                if(!pass) continue;
                //如果前置城市都去过了，则跳到下一个mask
                mydp[mask|1<<i]=mydp[mask]+A[i];
            }
        }
        int myres=0;
        for(int mask=0;mask<(1<<N);mask++)
        {   //如果旅游开销不大于V，则计算对应的最大的可去城市数
            if(mydp[mask]<=V)
            {
                myres=Math.max(myres,Integer.bitCount(mask));
            }
        }
        return myres; // 返回题目要求的结果
    }
}

复杂度分析
时间复杂度：两层循环嵌套mask二进制数组的递归，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：使用dp[ $图片说明$ ]大小的辅助数组，因此空间复杂度为 $O$ ( $图片说明$ )