# 568. Maximum Vacation Days

给一个N \* K的数组days，days\[i]\[j]表示第j天能在第i个城市休息的天数，每天能选一个城市休息，不过有些城市之间不能跳转，问最多能休息多少天。优化问题，能根据天数分成K个子问题，action为从上一天中选一个城市跳到另一个（可能一样的）城市，受限于从上个城市到这个城市的跳转能否成功。因此dp以天数和所在城市为状态，里头存在第i天在j城市累计最大休息天数。

```cpp
class Solution {
public:
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        const int N = days.size(), K = days[0].size();
        vector<vector<int>> dp(K, vector<int>(N, -1));
        dp[0][0] = days[0][0];
        for (int j = 1; j < N; ++j) {
            if (flights[0][j] == 0) continue;
            dp[0][j] = days[j][0];
        }
        for (int i = 1; i < K; ++i) {
            for (int j = 0; j < N; ++j) {
                for (int k = 0; k < N; ++k) {
                    if (dp[i - 1][k] == -1 || k != j && flights[k][j] == 0) continue;
                    dp[i][j] = max(dp[i][j], dp[i - 1][k] + days[j][i]); 
                }
            }
        }
        int res = 0;
        for (int j = 0; j < N; ++j) {
            res = max(res, dp[K - 1][j]);
        }
        return res;
    }
};
```