题解 | #旅行Ⅱ#

思路：

题目的主要信息：

• 一个N个城市，A数组中记录的是访问每个城市所需的花费，V是初始所有的总预算
• 如果同时访问了两个城市，需要满足List中Point记录的先后顺序
• 求满足预算条件下，最多访问的城市数

方法一：暴力法（超时）
具体做法：
利用next_permutation函数对1-N个城市进行全排列，然后检查这种排列是否符合预算与访问顺序。访问顺序可以用一个二维vector保存，一维是后访问的城市，二维是其前序访问城市。

class Solution {
public:
    int Travel(int N, int V, vector<int>& A, vector<Point>& List) {
        int res = 0;
        vector<vector<int> > city(N + 1);  
        vector<int> B(N + 1);
        for(int i = 0; i < List.size(); i++)
            city[List[i].y].push_back(List[i].x); //记录城市的先后顺序
        for(int i = 1; i <= N; i++) 
            B[i] = i; //排列组合
        do{
            int sum = 0;
            int rest = V;  //剩余的钱
            vector<bool> flag(N + 1, false); //记录访问过的记录
            for(int i = 1; i <= N; i++){
                for(int j = 0; j < city[B[i]].size(); j++)
                    if(!flag[city[B[i]][j]])  //访问顺序中已经访问过了
                        break;
                if(rest >= A[B[i] - 1]){ //可以继续访问
                    sum++;
                    rest -= A[B[i] - 1];
                }else
                    break;
                flag[B[i]] = true;
            }
            res = max(res, sum);
        }while(next_permutation(B.begin() + 1, B.end())); //全排列
        return res;
    }
};

复杂度分析：

• 时间复杂度：，全排列为，里面是两层循环
• 空间复杂度：，辅助数组city最坏情况是的二维辅助矩阵

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

class Solution {
public:
    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 << i) & m) > 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) {
        vector<int> dp(1 << N, 0); //一共2^N个状态
        vector<vector<int> > city(N, vector<int>()); //记录城市的先后顺序
        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);
    }
};

复杂度分析：

• 时间复杂度：，一共个状态，递归中需要循环的部分其实只有dp数组的大小，其他的都是直接返回
• 空间复杂度：，其中dp长度为为，city最坏为