Maximum Vacation Days - Leetcode Solution

Problem statement:

Given a 2D array of costs of staying in various cities (represented as integers), you need to find the maximum number of vacation days you can get by visiting any sequence of cities. While traversing from one city to another adjacent city, you must take a vacation on the day of arrival and then continue the journey the next day. You start your journey from the city 0, and you need to reach the last city N-1 where N is the total number of cities.

Approach:

We can use dynamic programming to solve this problem. Let dp[i][j] represent the maximum vacation days that can be achieved if we start from city i on day j.

If we are at city i on day j and we want to move to another city k, then we can only do so if we have enough vacation days left to spend for the day of arrival. If we have enough vacation days left, then we can update dp[k][j+1] = max(dp[k][j+1], dp[i][j] + cost[k][j+1]) where cost[k][j+1] is the cost of staying in city k on day j+1.

Finally, the answer is max(dp[i][j]) for i = 0 to N-1 and j = 0 to K-1 where K is the maximum number of days we can spend on vacation.

Code:

Here is the python code to solve the Maximum Vacation Days problem on LeetCode:

def maxVacationDays(flights: List[List[int]], days: List[List[int]]) -> int:
    N = len(flights)
    K = len(days[0])
    dp = [[float('-inf')] * K for _ in range(N)]
    dp[0][0] = 0
    for j in range(K):
        for i in range(N):
            if dp[i][j] == -float('inf'):
                continue
            for k in range(N):
                if i == k or flights[i][k] == 1:
                    dp[k][j+1] = max(dp[k][j+1], dp[i][j] + days[k][j])
    return max(dp[i][K-1] for i in range(N))

Explanation:

The code first initializes dp to all -inf except for dp[0][0] which is 0 because we start at city 0 on day 0. We then run a loop over all days j and cities i for each day. If dp[i][j] is -inf, then we skip to the next iteration. Otherwise, we loop over all cities k to check if we can move from city i to city k on day j. If the flight exists and we have enough vacation days to spend, then we update dp[k][j+1] accordingly.

Finally, we return the maximum vacation days that can be achieved by starting from any city and spending any sequence of days.

1