[Hard] 568. Maximum Vacation Days

LeetCode wants to give one of its best employees the option to travel among n cities to collect algorithm problems. But all work and no play makes Jack a dull boy, you could take vacations in some particular cities and weeks. Your job is to schedule the traveling to maximize the number of vacation days you could take, but there are certain rules and restrictions you need to follow.

Rules and restrictions:

You can only travel among n cities, represented by indexes from 0 to n - 1. Initially, you are in city 0 on Monday.
The cities are connected by flights. The flights are represented as an n x n matrix (not necessarily symmetrical), called flights, representing the airline status from the city i to the city j. If there is no flight from the city i to the city j, flights[i][j] = 0; Otherwise, flights[i][j] = 1. Also, flights[i][i] = 0 for all i.
You totally have k weeks (each week has 7 days) to travel. You can only take flights at most once per day and can only take flights on each Monday morning. Since flight time is so short, we don’t consider the impact of flight time.
For each city, you can only have restricted vacation days in different weeks, given an n x k matrix called days representing this relationship. For the value of days[i][j], it represents the maximum number of vacation days you could take in the city i in the week j.

You’re given the flights matrix and days matrix, and you need to output the maximum number of vacation days you could take during k weeks.

Examples

Example 1:

Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
One of the best strategies is:
1st week: fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
2nd week: fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week: stay at city 2, and play 3 days and work 4 days.
Ans = 6 + 3 + 3 = 12.

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:
Since there are no flights that enable you to move to another city, you have to stay at city 0 for the whole 3 weeks.
For each week, you only have one day off, so the maximum number of vacation days is 3.

Constraints

n == flights.length
n == flights[i].length
n == days.length
k == days[i].length
1 <= n, k <= 100
flights[i][j] is 0 or 1.
0 <= days[i][j] <= 7

Thinking Process

Rules and restrictions:

Define state: what subproblem does dp[i] (or dp[i][j]) represent?
Recurrence: how does the answer build from smaller indices?
Base cases first; optimize space if only prior row/layer is needed.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
1D DP (this problem)	O(n)	O(n) or O(1)	Linear recurrence
2D DP	O(nm)	O(nm) or O(n)	Grid or two-sequence problems
State machine DP	O(n)	O(1)	Buy/sell, hold/not-hold states
Memoization (top-down)	Same as DP	O(n)	Recursive + cache

Solution

Solution: Dynamic Programming (Bottom-Up)

class Solution:
    def maxVacationDays(self, flights, days):
        if not flights or not days:
            return 0

        n = len(flights)
        m = len(days[0])

        # dp[city] = max vacation starting from this city
        dp = [-float('inf')] * n
        dp[0] = 0

        for week in range(m - 1, -1, -1):
            temp = [-float('inf')] * n

            for cur_city in range(n):
                # option 1: stay in same city
                temp[cur_city] = days[cur_city][week] + dp[cur_city]

                # option 2: come from any city that can fly here
                for dest_city in range(n):
                    if flights[cur_city][dest_city]:
                        temp[cur_city] = max(
                            temp[cur_city],
                            days[dest_city][week] + dp[dest_city]
                        )

            dp = temp

        return dp[0]

Solution Explanation

Approach: 1D DP (this problem)

Key idea: LeetCode wants to give one of its best employees the option to travel among n cities to collect algorithm problems. But all work and no play makes Jack a dull boy, you could take vacations in some particular cities and weeks. Your job is to schedule the traveling to maximize the number of vacation days you could take, but there are certain rules and restrictions you need to follow.

How the code works: Rules and restrictions:

Define state: what subproblem does dp[i] (or dp[i][j]) represent?
Recurrence: how does the answer build from smaller indices?
Base cases first; optimize space if only prior row/layer is needed.

Walkthrough — input flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]], expected output 12:

One of the best strategies is: 1st week: fly from city 0 to city 1 on Monday, and play 6 days and work 1 day. 2nd week: fly from city 1 to city 2 on Monday, and play 3 days and work 4 days. 3rd week: stay at city 2, and play 3 days and work 4 days. Ans = 6 + 3 + 3 = 12.

Algorithm Explanation:

Edge Case (Line 4): Return 0 if inputs are empty
Initialization (Lines 5-6):
- N: Number of cities
- M: Number of weeks
- dp[i]: Maximum vacation days from week week+1 to end, ending at city i
Bottom-Up DP (Lines 7-17):
- Process weeks backwards: From last week to first week
- For each city (Lines 9-16):
  - Stay option: temp[cur_city] = days[cur_city][week] + dp[cur_city]
    - Stay in current city, add current week’s days, plus future optimal
  - Fly option: Check all cities with flights from current city
    - If flight exists: max(days[dest_city][week] + dp[dest_city], temp[cur_city])
    - Fly to destination, add destination’s days, plus future optimal
- Update DP: dp = move(temp) for next iteration
Result (Line 18): Return dp[0] - maximum starting from city 0

Example Walkthrough:

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

N = 3 cities, M = 3 weeks

Step 1: Week 2 (last week)
dp = [0, 0, 0] (no future weeks)

For city 0:
  Stay: days[0][2] + dp[0] = 1 + 0 = 1
  Fly to 1: days[1][2] + dp[1] = 3 + 0 = 3
  Fly to 2: days[2][2] + dp[2] = 3 + 0 = 3
  temp[0] = max(1, 3, 3) = 3

For city 1:
  Stay: days[1][2] + dp[1] = 3 + 0 = 3
  Fly to 0: days[0][2] + dp[0] = 1 + 0 = 1
  Fly to 2: days[2][2] + dp[2] = 3 + 0 = 3
  temp[1] = max(3, 1, 3) = 3

For city 2:
  Stay: days[2][2] + dp[2] = 3 + 0 = 3
  Fly to 0: days[0][2] + dp[0] = 1 + 0 = 1
  Fly to 1: days[1][2] + dp[1] = 3 + 0 = 3
  temp[2] = max(3, 1, 3) = 3

dp = [3, 3, 3]

Step 2: Week 1
For city 0:
  Stay: days[0][1] + dp[0] = 3 + 3 = 6
  Fly to 1: days[1][1] + dp[1] = 0 + 3 = 3
  Fly to 2: days[2][1] + dp[2] = 3 + 3 = 6
  temp[0] = max(6, 3, 6) = 6

For city 1:
  Stay: days[1][1] + dp[1] = 0 + 3 = 3
  Fly to 0: days[0][1] + dp[0] = 3 + 3 = 6
  Fly to 2: days[2][1] + dp[2] = 3 + 3 = 6
  temp[1] = max(3, 6, 6) = 6

For city 2:
  Stay: days[2][1] + dp[2] = 3 + 3 = 6
  Fly to 0: days[0][1] + dp[0] = 3 + 3 = 6
  Fly to 1: days[1][1] + dp[1] = 0 + 3 = 3
  temp[2] = max(6, 6, 3) = 6

dp = [6, 6, 6]

Step 3: Week 0 (first week)
For city 0 (starting city):
  Stay: days[0][0] + dp[0] = 1 + 6 = 7
  Fly to 1: days[1][0] + dp[1] = 6 + 6 = 12
  Fly to 2: days[2][0] + dp[2] = 3 + 6 = 9
  temp[0] = max(7, 12, 9) = 12

dp = [12, ...]

Result: dp[0] = 12

Optimal path:
Week 0: City 0 → City 1 (fly), days = 6
Week 1: City 1 → City 2 (fly), days = 3
Week 2: City 2 (stay), days = 3
Total: 6 + 3 + 3 = 12

Algorithm Breakdown

Key Insight: Bottom-Up DP

The algorithm processes weeks backwards (from end to beginning):

Base case: Last week - no future weeks, only current week’s days
Recursive case: For each week, consider all options and choose maximum
State: dp[city] = maximum vacation days from current week to end, ending at city

State Transition

For each city in each week:

Stay option: Stay in current city
- days[cur_city][week] + dp[cur_city]
Fly option: Fly to any city with available flight
- days[dest_city][week] + dp[dest_city]
Choose maximum: max(stay, all_fly_options)

Why Backward Processing Works

Processing backwards ensures:

When computing week i, we already know optimal for weeks i+1 to M-1
dp[city] represents future optimal value
Current week’s decision uses future optimal values

Complexity

Time Complexity: O(M × N²)

Outer loop: O(M) - iterate through each week
City loop: O(N) - for each city
Flight check: O(N) - check all possible destinations
Total: O(M × N²) where M = weeks, N = cities

Space Complexity: O(N)

DP array: O(N) - stores maximum for each city
Temporary array: O(N) - used for current week
Total: O(N) - space-optimized (only current state needed)

Key Points

Bottom-Up DP: Process weeks from end to beginning
State Optimization: Only store current week’s state (O(N) space)
Two Options: Stay in same city or fly to another city
Optimal Substructure: Optimal solution uses optimal subproblems
Starting City: Result is dp[0] since we start in city 0

Detailed Example Walkthrough

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

N = 3 cities, M = 3 weeks
No flights available (all 0s)

Step 1: Week 2
For each city, can only stay:
  dp[0] = days[0][2] = 1
  dp[1] = days[1][2] = 7
  dp[2] = days[2][2] = 7

Step 2: Week 1
For city 0: Stay only → dp[0] = 1 + 1 = 2
For city 1: Stay only → dp[1] = 7 + 7 = 14
For city 2: Stay only → dp[2] = 7 + 7 = 14

Step 3: Week 0
For city 0 (starting): Stay only → dp[0] = 1 + 2 = 3

Result: 3

Edge Cases

No flights: Can only stay in starting city
Single city: Only one city, no travel options
Single week: Only one week to maximize
All zeros: No vacation days available
All maximum: Maximum vacation days in all cities

Optimization Notes

The solution uses space optimization:

Instead of dp[week][city] (O(M × N) space)
Uses dp[city] and temp[city] (O(N) space)
Processes one week at a time, reusing space

Common Mistakes

Skipping edge cases (empty input, single element, boundaries).
Off-by-one errors in loops and index ranges.
Forgetting to handle the case when no valid answer exists.

568. Maximum Vacation Days - Current problem
787. Cheapest Flights Within K Stops - Similar DP with flights
64. Minimum Path Sum - DP on grid
120. Triangle - DP optimization

Key Takeaways

Rules and restrictions:**
Define state: what subproblem does dp[i] (or dp[i][j]) represent?
Recurrence: how does the answer build from smaller indices?

References

LC 568: Maximum Vacation Days on LeetCode
LeetCode Discuss — LC 568: Maximum Vacation Days
LeetCode Editorial (may require premium)

Template Reference

Graph

Robina Li

[Hard] 568. Maximum Vacation Days

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution: Dynamic Programming (Bottom-Up)

Solution Explanation

Algorithm Explanation:

Example Walkthrough:

Algorithm Breakdown

Key Insight: Bottom-Up DP

State Transition

Why Backward Processing Works

Complexity

Time Complexity: O(M × N²)

Space Complexity: O(N)

Key Points

Detailed Example Walkthrough

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

Edge Cases

Optimization Notes

Common Mistakes

Tags

Key Takeaways

References

Template Reference

Related Posts

Recent Posts

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution: Dynamic Programming (Bottom-Up)

Solution Explanation

Algorithm Explanation:

Example Walkthrough:

Algorithm Breakdown

Key Insight: Bottom-Up DP

State Transition

Why Backward Processing Works

Complexity

Time Complexity: O(M × N²)

Space Complexity: O(N)

Key Points

Detailed Example Walkthrough

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

Edge Cases

Optimization Notes

Common Mistakes

Related Problems

Tags

Key Takeaways

References

Template Reference

Related Posts

Recent Posts

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