去N个城市旅行，去每个城市的开销是Ai元。去y城市之前先旅游x城市，列出这些限制条件List。只有V元，最多能到多少个城市去旅游。
给定N, V，A数组，List数组
其中List 指明 x y 即访问y城市前必须先访问x城市
一行一个数字表示输出牛妹能去的最多城市数目
示例1
复制
3,10,[3,7,8],[(1,2)]复制
2
本问题和旅行1问题【旅行1】问题不同之处在于：
旅行1问题每当遇到多个可选城市时，一定是选择花费最少的那个，所以其求解过程是确定的，因此可以采取拓扑排序的方式。
旅行2问题每当遇到多个可选城市时，无法知道选哪个，因为无法保证选择花费少的那个城市之后能选到城市最多。
因此旅行2问题是搜索问题，搜索所有可行解中的最小值。
该搜索问题存在大量的重复计算情况：
如按照 A B C旅行完后到达某个状态T1
若按照B C A也能旅行，那么其到达的状态T2 T2和T1的状态是一致的（花费一样，剩余城市和钱也一样）
然而，到达T1状态后 继续搜索的过程，在到达T2时无需重复进行。
因此需要一个状态描述： 记录以及旅游过的城市。考虑采取位标记方式：
初始化，N个bit位全为0（由于总共城市不超过20 那么一个int 32位即可描述）int status=0若第i个城市被访问，那么 将status的第i位标记为1 方式： status | (1<<i) 按位或运算当希望访问i城市时，其前序城市一定全部已经被访问过，也就是对应bit位为1 采取 status & (1<<j) 进行判断 class Solution { public: int ans=0; vector<int> mp[21]; bool visit[1<<20]={false}; //visit数组 void dfs(int status,int* A,int N,int V,int depth) { if(visit[status]) return; ans=max(ans,depth);//更新最大值 visit[status]=true; for(int i=0;i<N;i++) { //分析i城市能否作为下一个访问城市 //当前的钱足够 并且 i城市没有被访问过（对应第i个二进制位为0） if(V>=A[i] && !(status&(1<<i))) { bool can=true; //确保i的所有前序城市 mp[i][j] 都被访问了 for(int j=0;j<mp[i].size();j++) { if((status & (1<<mp[i][j]))==0) //存在一个前序城市没有被访问 { can=false; break; } } if(can) { status=(status|(1<<i));//将第i个二进制位设置为1 dfs(status,A,N,V-A[i],depth+1);//进入下一层搜索 } } } } int Travel(int N, int V, int* A, int ALen, vector<Point>& list) { // write code here for(int i=0;i<list.size();i++) { int x=list[i].x-1; int y=list[i].y-1; mp[y].push_back(x);//mp[y]存放y的所有前序节点 } dfs(0,A,N,V,0); return ans; } };
DFS是一类搜索问题，从各个可能的入口寻找可行解，但搜索过程中可能存在大量的重复搜索过程。而采取记忆化搜索的方式可以避免重复的搜索计算，实现性能提升，主要有采取备忘录的方法（记忆和搜索）实现小问题的快速答案返回。
