• Time:O(N^2K)
• Space:O(NK)

## C++

``````class Solution {
public:
int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
// dp[i][j] := # of vacations can be taken from i-th city and k-th week
dp.resize(days.size(), vector<int>(days[0].size(), INT_MIN));
return maxVacationDays(flights, days, 0, 0);
}

private:
vector<vector<int>> dp;

int maxVacationDays(const vector<vector<int>>& flights,
const vector<vector<int>>& days, int i, int k) {
if (k == days[0].size())
return 0;
if (dp[i][k] != INT_MIN)
return dp[i][k];

int ans = 0;

// stay at j or fly from i -> j
for (int j = 0; j < flights.size(); ++j)
if (j == i || flights[i][j] == 1)
ans = max(ans, days[j][k] + maxVacationDays(flights, days, j, k + 1));

return dp[i][k] = ans;
}
};
``````

## JAVA

``````class Solution {
public int maxVacationDays(int[][] flights, int[][] days) {
// dp[i][j] := # of vacations can be taken from i-th city and k-th week
dp = new int[days.length][days[0].length];
Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MIN_VALUE));
return maxVacationDays(flights, days, 0, 0);
}

private int[][] dp;

private int maxVacationDays(int[][] flights, int[][] days, int i, int k) {
if (k == days[0].length)
return 0;
if (dp[i][k] != Integer.MIN_VALUE)
return dp[i][k];

int ans = 0;

// stay at j or fly from i -> j
for (int j = 0; j < flights.length; ++j)
if (j == i || flights[i][j] == 1)
ans = Math.max(ans, days[j][k] + maxVacationDays(flights, days, j, k + 1));

return dp[i][k] = ans;
}
}
``````

• Time:O(N^2K)
• Space:O(NK)

## C++

``````class Solution {
public:
int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
const int N = days.size();
const int K = days[0].size();
// dp[i][j] := # of vacations can be taken from i-th city and k-th week
vector<vector<int>> dp(N, vector<int>(K + 1));

for (int k = K - 1; k >= 0; --k)
for (int i = 0; i < N; ++i) {
dp[i][k] = days[i][k] + dp[i][k + 1];
for (int j = 0; j < N; ++j)
if (flights[i][j] == 1)
dp[i][k] = max(dp[i][k], days[j][k] + dp[j][k + 1]);
}

return dp[0][0];
}
};
``````

## JAVA

``````class Solution {
public int maxVacationDays(int[][] flights, int[][] days) {
final int N = days.length;
final int K = days[0].length;
// dp[i][j] := # of vacations can be taken from i-th city and k-th week
int[][] dp = new int[N][K + 1];

for (int k = K - 1; k >= 0; --k)
for (int i = 0; i < N; ++i) {
dp[i][k] = days[i][k] + dp[i][k + 1];
for (int j = 0; j < N; ++j)
if (flights[i][j] == 1)
dp[i][k] = Math.max(dp[i][k], days[j][k] + dp[j][k + 1]);
}

return dp[0][0];
}
}
``````

• Time:O(N^2K)
• Space:O(N)

## C++

``````class Solution {
public:
int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
const int N = days.size();
const int K = days[0].size();
// dp[i] := # of vacations can be taken from i-th city
vector<int> dp(N);

for (int k = K - 1; k >= 0; --k) {
vector<int> newDp(N);
for (int i = 0; i < N; ++i) {
newDp[i] = days[i][k] + dp[i];
for (int j = 0; j < N; ++j)
if (flights[i][j] == 1)
newDp[i] = max(newDp[i], days[j][k] + dp[j]);
}
dp = move(newDp);
}

return dp[0];
}
};
``````

## JAVA

``````class Solution {
public int maxVacationDays(int[][] flights, int[][] days) {
final int N = days.length;
final int K = days[0].length;
// dp[i] := # of vacations can be taken from i-th city
int[] dp = new int[N];

for (int k = K - 1; k >= 0; --k) {
int[] newDp = new int[N];
for (int i = 0; i < N; ++i) {
newDp[i] = days[i][k] + dp[i];
for (int j = 0; j < N; ++j)
if (flights[i][j] == 1)
newDp[i] = Math.max(newDp[i], days[j][k] + dp[j]);
}
dp = newDp;
}

return dp[0];
}
}
``````