568. Maximum Vacation Days

解题思路：这是一道在图上做有记忆dfs的题目，图的信息通过矩阵给出。一共有N个城市，城市之间的连同关系在 flights 矩阵中，代表着dfs中下一次递归的可行选择。另外一个给出的信息是K个星期中在每一个城市可以得到的假期数量，题目要求找出K个星期中最多的假期，这也是每次递归中需要累加的值，K也是递归终止的条件。

为了节省时间复杂度，需要另外分配一个memo的矩阵将之前计算过的值保留，如果这个值不为 0 每次递归直接返回。

注意：给出的航班信息表中没有每个城市到自己的航班，即flight[i][i] 为0 ，这个符合常识，但并不符合题意。因为两个星期之间并不一定非要飞到另外一个城市，如果呆在本地假期更多也可以不飞，需要做一个预先的处理就是将 flights[i][i] 全部置为1。

时间复杂度：这个取决于矩阵的稀疏程度，也就是到下一个城市可以的选择，这个有由flights 矩阵给出，假设每两个城市之间都有相互连接的航班，共需要做K次的选择，每次计算后将结果保存避免不必要的时间消耗，最终的复杂度为 O(N * K)

空间复杂度：为每个城市在每个星期分配一个变量保存计算过的值，复杂度 O(N * K)

class Solution {
public:
    int recursive(int week, int city, vector<vector<int>>& memo, const vector<vector<int>>& flights, const vector<vector<int>>& days){
        if(week == days[0].size() - 1){
            return days[city][week];
        }
        if(memo[city][week] > 0){
            return memo[city][week];
        }
        for(int next = 0; next < flights[city].size(); ++next){
            if(flights[city][next] == 1){
                memo[city][week] = max(memo[city][week], days[city][week] + recursive(week + 1, next, memo, flights, days));
            }
        }
        return memo[city][week];
    }
    
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        const int cityCnt = days.size();
        const int weekCnt = days[0].size();
        vector<vector<int>> memo(cityCnt, vector<int>(weekCnt, 0));
        for(int i = 0; i < flights.size(); ++i){
            flights[i][i] = 1;
        }
        int maxVocation = 0; 
        for(int i = 0; i < flights[0].size(); ++i){
            if(flights[0][i] == 1){
                 maxVocation = max(maxVocation, recursive(0, i, memo, flights, days));
            }
        }
        return maxVocation;
    }
};