# 568. Maximum Vacation Days     ## Approach 1: Top-down

• Time: $O(N^2K)$
• Space: $O(NK)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: int maxVacationDays(vector>& flights, vector>& days) { // dp[i][j] := # of vacations can be taken from i-th city and k-th week dp.resize(days.size(), vector(days.size(), INT_MIN)); return maxVacationDays(flights, days, 0, 0); } private: vector> dp; int maxVacationDays(const vector>& flights, const vector>& days, int i, int k) { if (k == days.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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 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.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.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; } } 

## Approach 2: Bottom-up 2D DP

• Time: $O(N^2K)$
• Space: $O(NK)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public: int maxVacationDays(vector>& flights, vector>& days) { const int N = days.size(); const int K = days.size(); // dp[i][j] := # of vacations can be taken from i-th city and k-th week vector> dp(N, vector(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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int maxVacationDays(int[][] flights, int[][] days) { final int N = days.length; final int K = days.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; } } 

## Approach 3: Bottom-up 1D DP

• Time: $O(N^2K)$
• Space: $O(N)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: int maxVacationDays(vector>& flights, vector>& days) { const int N = days.size(); const int K = days.size(); // dp[i] := # of vacations can be taken from i-th city vector dp(N); for (int k = K - 1; k >= 0; --k) { vector 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int maxVacationDays(int[][] flights, int[][] days) { final int N = days.length; final int K = days.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; } }