Leetcode 568. Maximum Vacation Days

Problem

You're planning an extended vacation across multiple cities over several weeks. You start in city 0 and need to maximize the total number of vacation days you can enjoy.

You are given:

• A 2D array flights where flights[i][j] equals 1 if there is a direct flight from city i to city j, and 0 otherwise. Note that flights[i][i] equals 0 or 1, indicating whether you can stay in city i.
• A 2D array days where days[i][k] represents the number of vacation days you can enjoy in city i during week k.

At the beginning of each week, you can choose to either:

• Stay in your current city (if flights[currentCity][currentCity] equals 1 or you just want to stay), or
• Fly to another city j (if flights[currentCity][j] equals 1)

Return the maximum number of vacation days you can accumulate over all weeks.

Requirements

1. You must start at city 0
2. You can only travel along routes where flights[i][j] equals 1
3. Each week, you collect vacation days based on which city you're in
4. You must decide your location at the start of each week
5. Return the maximum total vacation days possible

Constraints

• n == flights.length (number of cities)
• n == flights[i].length
• n == days.length
• k == days[i].length (number of weeks)
• 1 <= n, k <= 100
• flights[i][j] is either 0 or 1
• 0 <= days[i][j] <= 7

Examples

Example 1:

` Input: flights = [[0,1],[1,0]], days = [[1,3],[3,2]] Output: 7 Explanation:

• Start at city 0
• Week 0: Fly to city 1, collect 3 vacation days
• Week 1: Stay at city 1, collect 2 vacation days
• Total: 3 + 2 = 7 vacation days `

Example 2:

` Input: flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[7,7,7]] Output: 3 Explanation:

• No flights available between cities
• Must stay at city 0 for all 3 weeks
• Total: 1 + 1 + 1 = 3 vacation days `

Example 3:

` Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[3,1,3],[1,3,1]] Output: 12 Explanation:

• Start at city 0
• Week 0: Fly to city 1, collect 3 vacation days
• Week 1: Fly to city 2, collect 3 vacation days
• Week 2: Fly to city 1, collect 3 vacation days
• Alternative optimal paths exist, total: 12 vacation days `

Hint 1: Problem Structure Think of this as a graph traversal problem over time. At each week, you're at some city, and you need to decide which city to be at next week based on available flights. This naturally suggests a dynamic programming approach where the state is (city, week).

Hint 2: State Definition Define dp[city][week] as the maximum vacation days you can collect if you are at city at the start of week. Think about how to transition from week to week: from any city in week w, you can move to any reachable city (via flights) for week w+1.

Hint 3: Base Case and Transitions Base case: You start at city 0 at week 0. For each subsequent week, consider all cities you could have been at in the previous week, and all cities you can fly to from there. The vacation days collected depend on where you are during that week.

Full Solution `` Explanation:

The solution uses dynamic programming to explore all possible itineraries:

1. State Definition: dp[city][week] represents the maximum vacation days achievable if we are at city at the start of week.
2. Initialization: We start at city 0 in week 0. We also check if we can immediately fly to other cities in week 0.
3. Transitions: For each week and each city, we consider all possible previous cities we could have been at. If there's a valid flight path (or we're staying in the same city), we update the DP value by adding the vacation days for the current city and week.
4. Result: The answer is the maximum value across all cities in the final week.

Time Complexity: O(n² × k) where n is the number of cities and k is the number of weeks. For each of the k weeks, we consider all n cities, and for each city, we check all n possible previous cities.

Space Complexity: O(n × k) for the DP table. This can be optimized to O(n) by only keeping track of the previous week's state.

def maxVacationDays(flights: list[list[int]], days: list[list[int]]) -> int:
    n = len(flights)  # number of cities
    k = len(days[0])  # number of weeks
    
    # dp[city][week] = max vacation days when at 'city' at start of 'week'
    # Initialize with -1 to indicate unreachable states
    dp = [[-1] * k for _ in range(n)]
    
    # Base case: start at city 0 at week 0
    dp[0][0] = days[0][0]
    
    # Also consider flying from city 0 to other cities in week 0
    for dest in range(n):
        if flights[0][dest] == 1:
            dp[dest][0] = days[dest][0]
    
    # Fill the DP table for each subsequent week
    for week in range(1, k):
        for city in range(n):
            # Try coming from each possible previous city
            for prev_city in range(n):
                # Can only come from prev_city if:
                # 1. We were at prev_city last week (dp[prev_city][week-1] != -1)
                # 2. There's a flight from prev_city to city (or they're the same and we can stay)
                if dp[prev_city][week - 1] != -1:
                    can_reach = (prev_city == city) or (flights[prev_city][city] == 1)
                    if can_reach:
                        new_total = dp[prev_city][week - 1] + days[city][week]
                        dp[city][week] = max(dp[city][week], new_total)
    
    # Find the maximum vacation days across all cities in the last week
    max_days = 0
    for city in range(n):
        if dp[city][k - 1] != -1:
            max_days = max(max_days, dp[city][k - 1])
    
    return max_days