Solution 1. DFS. The idea is just try each `possible`

city for every week and keep tracking the `max`

vacation days. Time complexity O(N^K). Of course it will TLE....

```
public class Solution {
int max = 0, N = 0, K = 0;
public int maxVacationDays(int[][] flights, int[][] days) {
N = flights.length;
K = days[0].length;
dfs(flights, days, 0, 0, 0);
return max;
}
private void dfs(int[][] f, int[][] d, int curr, int week, int sum) {
if (week == K) {
max = Math.max(max, sum);
return;
}
for (int dest = 0; dest < N; dest++) {
if (curr == dest || f[curr][dest] == 1) {
dfs(f, d, dest, week + 1, sum + d[dest][week]);
}
}
}
}
```

Solution 2. DP. `dp[i][j]`

stands for the max vacation days we can get in week `i`

staying in city `j`

. It's obvious that `dp[i][j] = max(dp[i - 1][k] + days[j][i]) (k = 0...N - 1, if we can go from city k to city j)`

. Also because values of week `i`

only depends on week `i - 1`

, so we can compress two dimensional `dp`

array to one dimension. Time complexity O(K * N * N) as we can easily figure out from the 3 level of loops.

```
public class Solution {
public int maxVacationDays(int[][] flights, int[][] days) {
int N = flights.length;
int K = days[0].length;
int[] dp = new int[N];
Arrays.fill(dp, Integer.MIN_VALUE);
dp[0] = 0;
for (int i = 0; i < K; i++) {
int[] temp = new int[N];
Arrays.fill(temp, Integer.MIN_VALUE);
for (int j = 0; j < N; j++) {
for(int k = 0; k < N; k++) {
if (j == k || flights[k][j] == 1) {
temp[j] = Math.max(temp[j], dp[k] + days[j][i]);
}
}
}
dp = temp;
}
int max = 0;
for (int v : dp) {
max = Math.max(max, v);
}
return max;
}
}
```