Leetcode 568. Maximum Vacation Days

The problem asks us to find the maximum number of vacation days we could take during K weeks. The vacation days are restricted by 2 conditions -

1. We can only travel among N cities where each city is represented by an index from 0 to n-1 and we start with the index 0.

2. We can take at most one flight per day and we can only take flights on Monday morning. Therefore, our total travel is bounded by K weeks.

Each city has a restricted amount of vacation days for each week, which is represented by days[i][j] where it denotes the maximum days you could take a vacation in city i in the week j.

We're given a flights matrix denoting the airline status from city i to city j. If there is no flight from city i to city j then flights[i][j] = 0 otherwise if there is a flight from city i to city j then flights[i][j] = 1.

Example walk-through:

For the input

flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]

One strategy can look like this:

1. In 1st week : We fly from city 0 to city 1 on Monday, and play for 6 days and work 1 day. (Even though we start at city 0, we could also fly to and start at other cities since it is Monday.)
2. In 2nd week : We fly from city 1 to city 2 on Monday, and play for 3 days and work 4 days.
3. In 3rd week : We stay at city 2, and play for 3 days and work 4 days.

Therefore total maximum vacation days we could take becomes 6+3+3 = 12.

Approach to the Solution:

The problem requires a dynamic programming approach. The intuition is to have a dp[i][k] where it stores the maximum vacations that can be taken from i-th city and k-th week. Max number of vacations will be either staying in the current city or flying to a different city.

The maximum vacation days will be the maximum from the current value and the maximum vacation days from the next city and week.

Python solution:

1
2python
3class Solution:
4    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
5        N = len(flights) # the number of cities
6        K = len(days[0]) # total weeks
7        dp = [[-1 for _ in range(K)] for __ in range(N)] 
8        dp[0][0] = days[0][0] # initialization
9        for k in range(1, K): # for each week
10            for i in range(N): # for each city
11                dp[i][k] = max(dp[j][k - 1] + days[i][k] if dp[j][k - 1] >= 0 else -1 for j in range(N) if j == i or flights[j][i] == 1)
12
13        return max(dp[i][-1] for i in range(N))

Java solution:

1
2java
3class Solution {
4    public int maxVacationDays(int[][] flights, int[][] days) {
5        int N = flights.length;
6        int K = days[0].length;
7        int dp[][] = new int[N][K];
8        for (int i = 0; i < N; i++) {
9            for (int j = 0; j < K; j++) {
10                dp[i][j] = -1;
11            }
12        }
13        dp[0][0] = days[0][0];
14        for (int k = 1; k < K; k++) {
15            for (int i = 0; i < N; i++) {
16                for (int j = 0; j < N; j++) {
17                    if (j == i || flights[j][i] == 1) {
18                        dp[i][k] = Math.max(dp[i][k], (dp[j][k - 1] == -1 ? -1 : dp[j][k - 1] + days[i][k]));
19                    }
20                }
21            }
22        }
23        int answer = 0;
24        for (int i = 0; i < N; i++) {
25            answer = Math.max(answer, dp[i][K - 1]);
26        }
27        return answer;
28    }
29}

JavaScript solution:

1
2javascript
3var maxVacationDays = function(flights, days) {
4    let N = flights.length, K = days[0].length;
5    let dp = Array.from(Array(K + 1), () => Array.from(Array(N + 1), () => 0));
6
7    for (let k = K - 1; k >= 0; --k) {
8        for (let i = 0; i < N; ++i) {
9            dp[i][k] = Math.max(dp[i][k], days[i][k] + dp[i][k + 1]);
10
11            for (let j = 0; j < N; ++j) {
12                if (i !== j && flights[j][i]) {
13                    dp[j][k] = Math.max(dp[j][k], days[i][k] + dp[i][k + 1]);
14                }
15            }
16        }
17    }
18
19    return dp.reduce((acc, days, i) => Math.max(acc, flights[0][i] ? days[0] : 0), 0);
20};

C++ solution:

1
2c++
3class Solution {
4public:
5    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
6        int N = flights.size();
7        int K = days[0].size();
8        vector<vector<int>> dp(N, vector<int>(K, -1));
9        dp[0][0] = days[0][0];
10        
11        for(int k = 1; k < K; ++k){
12            for(int i = 0; i < N; ++i){
13                for(int j = 0; j < N; ++j){
14                    if(i==j || flights[j][i]==1)
15                        dp[i][k] = max(dp[i][k], dp[j][k-1]==-1?-1:days[i][k] + dp[j][k-1]);
16                }
17            }
18        }
19        return max_element(dp[0].begin(), dp[0].end());
20    }
21};

C# solution:

1
2csharp
3public class Solution {
4    public int MaxVacationDays(int[][] flights, int[][] days) {
5        int N = flights.Length, K = days[0].Length;
6
7        int[,] dp = new int[N,K];
8        for (int i = 0; i <dp.GetLength(0); i++)
9            for (int j = 0; j < dp.GetLength(1); j++)
10                dp[i,j] = -1;
11
12        dp[0,0] = days[0][0];
13
14        for (int k = 1; k < K; k++)
15            for (int i = 0; i < N; i++)
16                for (int j = 0; j < N; j++)
17                    if (i == j || flights[j][i] == 1)
18                        dp[i,k] = Math.Max(dp[i,k], dp[j,k - 1] == -1 ? -1: dp[j,k - 1] + days[i][k]);
19
20        int answer = 0;
21        for (int i = 0; i < N; i++)
22            answer = Math.Max(answer, dp[i,K - 1]);
23
24        return answer;
25    }
26}

We initialized the dp[][] to -1 as it indicates that some combination is not feasible or not possible. This helps us check if a vacation day is available in terms of city and week. The dp[i][k-1] represents the maximum vacation days achievable at city j at week k-1. If this value is -1, it means reaching to city j at week k-1 is not possible, then we should not consider this combination for week k.

Finally, we return the maximum value in dp[i][-1] (Java: dp[i][K-1]), which indicates the maximum number of vacation days we can enjoy in any city at the last week.

In the JavaScript solution, the looping is done in reverse order starting from the last week instead of the first week for calculation of vacation days. The end result is still the maximum number of vacation days.

The C++ solution provides the first argument of max_element() function as the beginning iterator and the second argument as the end iterator, and returns the maximum element in range. It allows us to easily get the maximum element in container like array, vector, set etc.

The C# solution is similar to the Java solution. It creates a 2D dp array with N rows and K columns. In C#, we have to initialize dp[i,k] manually to -1 for each i and k because C# does not support this kind of initialization like Python. The max is taken similar to the Java solution. What's different is how it gets the length of i and j dimension of the array. It uses the GetLength method where GetLength(0) returns the number of rows and GetLength(1) returns the number of columns.

Hence, the problem can be solved using dynamic programming where we calculate the maximum possible vacations for each city in every available week. We choose the maximum among these and carry it forward to calculate for the next week. We repeat this until we have calculated for all weeks and return the maximum possible vacation days at the end. This maximizes the total number of vacation days we can take given the restrictions.