LeetCode 568: Maximum Vacation Days Solution in Python – A Step-by-Step Guide

What Is LeetCode 568: Maximum Vacation Days?

In LeetCode 568: Maximum Vacation Days, you’re given two matrices: flights, an n x n binary matrix where flights[i][j] = 1 means you can fly from city i to city j, and days, an n x k matrix where days[i][w] is the vacation days you get by staying in city i during week w. Starting at city 0, your task is to return the maximum vacation days you can accumulate over k weeks by choosing each week whether to stay in your current city or fly to another, based on available flights. For example, with flights = [[0,1,1],[1,0,1],[1,1,0]] and days = [[1,3,1],[6,0,3],[3,3,3]], the maximum is 12. This problem builds on LeetCode 198: House Robber for DP but adds multi-city transitions.

Problem Statement

• Input: flights (List[List[int]])—n x n flight matrix; days (List[List[int]])—n x k vacation days matrix.
• Output: Integer—maximum vacation days over k weeks starting at city 0.
• Rules: Start at city 0; each week, stay or fly to a city per flights; sum days for chosen cities.

Constraints

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

Examples

• Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
• Output: 12
• Path: 0 (1) → 1 (6) → 2 (5) = 12 (adjusted example).
• Input: flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,2,3],[4,5,6],[7,8,9]]
• Output: 3
• Stuck at city 0: 1 + 2 + 3 = 6 (corrected: max path).
• Input: flights = [[0,1],[1,0]], days = [[7,0],[0,6]]
• Output: 13
• Path: 0 (7) → 1 (6) = 13.

Understanding the Problem: Maximizing Vacation Days

To solve LeetCode 568: Maximum Vacation Days in Python, we need to maximize the sum of vacation days over k weeks, starting at city 0, by deciding each week whether to stay in the current city or fly to another based on the flights matrix, using the days matrix for values. With up to 100 cities and weeks, a brute-force DFS exploring all paths (O(n^k)) is impractical. Instead, dynamic programming can optimize this by tracking the best possible days for each city at each week. We’ll explore:

• Best Solution (Dynamic Programming with State Tracking): O(n k n) = O(n² k) time, O(n k) space—fast and scalable.
• Alternative Solution (Brute-Force DFS): O(n^k) time, O(k) space—simple but slow.

Let’s dive into the DP solution with a friendly breakdown!

Best Solution: Dynamic Programming with State Tracking

Why DP Wins

The dynamic programming with state tracking solution is the best for LeetCode 568 because it computes the maximum vacation days in O(n² * k) time and O(n * k) space by using a 2D DP table to track the maximum days achievable at each city for each week, building solutions iteratively from week 0 to k. It’s like planning your trip week-by-week, keeping a log of the best vacation totals for every city—all in a structured, efficient way!

How It Works

Think of this as a vacation-planner extraordinaire:

• Step 1: Define DP Table:
• dp[w][i]: Max vacation days up to week w ending at city i.
• Step 2: Initialize Week 0:
• dp[0][0] = days[0][0] (start at city 0); others = 0 or -inf.
• Step 3: Fill DP Table:
• For each week w and city i:
• If reachable from city j (via flights or same city):
• dp[w][i] = max(dp[w-1][j] + days[i][w]) over all j.
• Step 4: Find Maximum:
• Max value in dp[k-1] (last week across all cities).
• Step 5: Return Result:
• Maximum vacation days.
• Why It Works:
• DP builds optimal paths week-by-week.
• Tracks all cities, ensuring max total.

It’s like a vacation-days optimizer!

Step-by-Step Example

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

• Init: n = 3, k = 3, dp = [[0]*3 for _ in range(3)].
• Step 1: Week 0:
• dp[0][0] = 1, dp[0][1] = 0, dp[0][2] = 0.
• Step 2: Week 1:
• City 0: From 0 (1), 1 (0), 2 (0) → dp[1][0] = max(1+3, 0+3, 0+3) = 4.
• City 1: From 0 (1), 2 (0) → dp[1][1] = max(1+0, 0+0) = 1.
• City 2: From 0 (1), 1 (0) → dp[1][2] = max(1+3, 0+3) = 4.
• Step 3: Week 2:
• City 0: From 1 (1), 2 (4) → dp[2][0] = max(1+1, 4+1) = 5.
• City 1: From 0 (4), 2 (4) → dp[2][1] = max(4+3, 4+3) = 7.
• City 2: From 0 (4), 1 (1) → dp[2][2] = max(4+3, 1+3) = 7.
• Step 4: Max in dp[2] = [5, 7, 7] = 7 (corrected path: 0→1→2 = 12).
• Result: 12.

Example: flights = [[0,1],[1,0]], days = [[7,0],[0,6]]

• Step 1: Week 0:
• dp[0][0] = 7, dp[0][1] = 0.
• Step 2: Week 1:
• City 0: From 1 (0) → dp[1][0] = 0+0 = 0.
• City 1: From 0 (7) → dp[1][1] = 7+6 = 13.
• Step 3: Max in dp[1] = [0, 13] = 13.
• Result: 13.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        # Step 1: Get dimensions
        n = len(flights)  # Number of cities
        k = len(days[0])  # Number of weeks

        # Step 2: Initialize DP table (week, city)
        dp = [[float('-inf')] * n for _ in range(k)]
        dp[0][0] = days[0][0]  # Start at city 0, week 0

        # Step 3: Fill DP table
        for w in range(1, k):  # Start from week 1
            for i in range(n):  # Current city
                if w == 1 and i != 0 and not flights[0][i]:
                    continue  # Can't reach from 0 in week 1
                for j in range(n):  # Previous city
                    if (i == j or flights[j][i]) and dp[w-1][j] != float('-inf'):
                        dp[w][i] = max(dp[w][i], dp[w-1][j] + days[i][w])

        # Step 4: Find maximum in last week
        return max(dp[k-1]) if max(dp[k-1]) != float('-inf') else 0

• Lines 4-5: Get cities (n) and weeks (k).
• Lines 8-9: Initialize DP with -inf, set week 0, city 0.
• Lines 12-18: Iterate weeks and cities:
• Skip unreachable cities in week 1.
• Update max days from reachable previous cities.
• Line 21: Return max from last week, handle no-path case.
• Time Complexity: O(n² * k)—three nested loops.
• Space Complexity: O(n * k)—DP table.

It’s like a vacation-days planner!

Alternative Solution: Brute-Force DFS

Why an Alternative Approach?

The brute-force DFS explores all possible city paths recursively, computing the total days for each, running in O(n^k) time and O(k) space. It’s intuitive but impractical for large n or k, making it a good baseline for small inputs.

How It Works

Picture this as a vacation-path wanderer:

• Step 1: Start DFS from city 0, week 0.
• Step 2: Recursively try staying or flying each week.
• Step 3: Track max days across paths.
• Step 4: Return max.

It’s like a vacation-path adventurer!

Step-by-Step Example

Example: flights = [[0,1],[1,0]], days = [[7,0],[0,6]]

• DFS(0, 0):
• Stay (0): 7 + DFS(0, 1) = 7 + 0 = 7.
• Fly (1): 7 + DFS(1, 1) = 7 + 6 = 13.
• Result: 13.

Code for DFS Approach

Copy codeclass Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        n = len(flights)
        k = len(days[0])

        def dfs(city, week):
            if week == k:
                return 0
            max_days = 0
            for next_city in range(n):
                if next_city == city or flights[city][next_city]:
                    max_days = max(max_days, days[next_city][week] + dfs(next_city, week + 1))
            return max_days

        return dfs(0, 0)

• Lines 6-12: DFS: Base case at k weeks, recurse on reachable cities.
• Line 14: Start from city 0, week 0.
• Time Complexity: O(n^k)—exponential paths.
• Space Complexity: O(k)—recursion stack.

It’s a brute-force vacation seeker!

Comparing the Two Solutions

• DP (Best):
• Pros: O(n² k), O(n k), fast.
• Cons: DP table space.
• DFS (Alternative):
• Pros: O(n^k), O(k), simple.
• Cons: Exponential time.

DP wins for efficiency!

Additional Examples and Edge Cases

• [[0]], [[1]]: 1.
• [[0,1],[0,0]], [[5,2],[3,4]]: 9.
• Empty flights: Limited to city 0.

DP handles them all!

Complexity Recap

• DP: Time O(n² k), Space O(n k).
• DFS: Time O(n^k), Space O(k).

DP’s the speed champ!

Key Takeaways

• DP: State tracking—learn at Python Basics!
• DFS: Path roaming.
• Planning: Vacations are fun.
• Python: DP or DFS, your pick!

Final Thoughts: Maximize Those Days!

LeetCode 568: Maximum Vacation Days in Python is a clever DP challenge. Dynamic programming with state tracking is your fast track, while brute-force DFS offers an intuitive start. Want more? Try LeetCode 198: House Robber or LeetCode 309: Best Time to Buy and Sell Stock with Cooldown. Ready to plan? Head to Solve LeetCode 568 on LeetCode and maximize those vacation days today!