# Java DFS(TLE) and DP Solutions

• 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;
}
}
``````

• @shawngao Nice solution!

• Thanks for sharing! I come out with the similar idea but haven't realized we can do some space optimization here.
Here is my O(NK) space solution.

``````public class Solution {

public int maxVacationDays(int[][] flights, int[][] days) {
int N = flights.length;
int K = days[0].length;
int[][] dp = new int[N][K];
boolean[][] canReach = new boolean[N][K];
int res = 0;
// init : week1 start from city 0
for (int i = 0; i < N; i++) {
if (i == 0 || flights[0][i] == 1) {
// System.out.printf(" we can fly from city %d to %d in week %d\n", 0, i, 0);
dp[i][0] = days[i][0];
canReach[i][0] = true;
}
}
// dp
for (int j = 1; j < K; j++) {
for (int i = 0; i < N; i++) {
for (int k = 0; k < N; k++) {
// we can fly from city k to i
if ((k == i || flights[k][i] == 1) && canReach[k][j - 1]) {
// System.out.printf(" we can fly from city %d to %d in week %d\n", k, i, j);
dp[i][j] = Math.max(dp[i][j], dp[k][j - 1] + days[i][j]);
canReach[i][j] = true;
}
}
}
}
for (int i = 0; i < N; i++) {
res = Math.max(res, dp[i][K - 1]);
}
return res;
}

}
``````

• @shawngao
Similar idea by using DP. The main difference is that I use DP backward.
The problem boils down to solving the following equation:
`V[i, k] = max( days[i][k] + V[i, k+1], days[j][k] + V[j][k+1])`, where `j` satisfies `j != i && flights[i][j] == 1`, for `i = 0, ... ,N-1, k = 0, ... , K-1`, and `V[i, k]` represent the maximum vocation days in City `i` begining from Week `k`.

Here is my code.

``````public int maxVacationDays(int[][] flights, int[][] days) {
if (days.length == 0 || flights.length == 0) return 0;
int N = flights.length;
int K = days[0].length;
int[][] vocationDays = new int[N][K + 1];
for (int k = K - 1; k >= 0; k--) {
for (int i = 0; i < N; i++) {
vocationDays[i][k] = days[i][k] + vocationDays[i][k + 1];
for (int j = 0; j < N; j++) {
if (flights[i][j] == 1) {
vocationDays[i][k] = Math.max(days[j][k] + vocationDays[j][k + 1], vocationDays[i][k]);
}
}
}
}
return vocationDays[0][0];
}
``````

• ``````public int maxVacationDays(int[][] flights, int[][] days) {
int N = flights.length, K = days[0].length, dp[] = new int[cities];
Arrays.fill(dp, 1, dp.length, -1);
for (int i = 0, j, k, temp[]; i < K; i++, dp = temp)
for (j = 0, temp = Arrays.copyOf(dp, dp.length); j < N; j++)
if (dp[j] >= 0) for (k = 0; k < N; k++)
if (j == k || flights[j][k] == 1) temp[k] = Math.max(temp[k], dp[j] + days[k][i]);
return Arrays.stream(dp).max().getAsInt();
}``````

• @shawngao why do not you consider the case that the person cannot arrive the `k` place at the `i -1` week? You just use `flights[k][j] == 1` to judge if he can arrive the `j` place at the `i` week. Maybe the graph is not connected.

• @Andrewli
I agree with you, the answer is correct only because Integer.MIN_VALUE has too much weight. If we have many more vocation days at the dis-connected city, the answer will be wrong.

• @hyj143 yes, and actually, this is bellman-ford algorithm. Many problems in leetcode are modified version of very classic algorithm problems, but I don't know why these author in discussion don't mention it.

• If you do DFS with cache, it could pass the OJ, my result is 600ms.

``````public int maxVacationDays(int[][] flights, int[][] days) {
int N = flights.length, K = days[0].length;
int[][] cache = new int[K][N];
for(int i=0; i<K; i++){
Arrays.fill(cache[i], -1);
}
return DFS(flights, days, 0, 0, cache);
}

private int DFS(int[][] flights, int[][] days, int k, int i, int[][] cache){
int N = flights.length, K = days[0].length;
if(k==K) return 0;
if(cache[k][i]>=0) return cache[k][i];
int max = 0;
for(int j=0; j<N; j++){
if(i==j || flights[i][j]==1){
int temp = DFS(flights, days, k+1, j, cache)+days[j][k];
max = Math.max(max, temp);
}
}
cache[k][i] = max;
return max;
}``````

• What is TLE with DFS ?

• @amit65 got it.Time limit Exceeded

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.