LeetCode 568: Maximum Vacation Days

A clear explanation of Maximum Vacation Days using dynamic programming over weeks and cities.

leetcodedynamic-programmingmatrixgraph

Problem Restatement

We are given two matrices:

Matrix Meaning
flights Whether we can fly from one city to another
days How many vacation days we can take in each city during each week

There are n cities, indexed from 0 to n - 1.

We start in city 0 on Monday morning before week 0.

Each week, we may either:

  1. Stay in the current city.
  2. Fly to another city if there is a direct flight.

Flights can only happen on Monday morning of each week. After choosing the city for that week, we gain days[city][week] vacation days.

Return the maximum total vacation days possible.

The original constraints are 1 <= n, k <= 100, flights[i][j] is 0 or 1, and days[i][j] is between 0 and 7. The flight matrix is not necessarily symmetric.

Input and Output

Item Meaning
Input flights, an n x n matrix
Input days, an n x k matrix
Output Maximum total vacation days
Start city City 0
Travel rule Stay or take one allowed flight at the start of each week

Example function shape:

def maxVacationDays(flights: list[list[int]], days: list[list[int]]) -> int:
    ...

Examples

Example 1:

flights = [
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0],
]

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

We start in city 0.

One good plan is:

Week City Vacation days
0 1 6
1 2 3
2 1 3

Total:

6 + 3 + 3 = 12

So the answer is:

12

Example 2:

flights = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0],
]

days = [
    [1, 1, 1],
    [7, 7, 7],
    [7, 7, 7],
]

There are no flights.

We must stay in city 0 every week.

So the answer is:

1 + 1 + 1 = 3

First Thought: Try Every Travel Plan

A direct solution is to recursively try every city choice for every week.

At each week, from the current city, we try:

  1. Staying.
  2. Flying to every reachable city.

This explores many possible schedules.

With up to 100 weeks and 100 cities, the number of possible paths is far too large.

We need dynamic programming because the same state appears many times.

Key Insight

At the beginning of a week, the future only depends on two things:

State Meaning
week Which week we are about to process
city Which city we are currently in

It does not matter how we reached that city. Only the best total vacation days so far matters.

So we define a DP state:

dp[city]

as the maximum vacation days we can have before the current week while being in city.

Then each week, we build a new array next_dp.

Transition

Suppose we are currently in city src.

During the next week, we can go to city dst if:

src == dst

or:

flights[src][dst] == 1

Then we can update:

next_dp[dst] = max(next_dp[dst], dp[src] + days[dst][week])

The vacation days come from the destination city, because we spend that week there.

Algorithm

  1. Let n = len(flights).
  2. Let k = len(days[0]).
  3. Initialize all cities as unreachable: 
    dp = [-inf] * n
  4. Set: 
    dp[0] = 0
  5. For each week:
    1. Create next_dp = [-inf] * n.
    2. For each source city src:
      1. If dp[src] is unreachable, skip it.
      2. For each destination city dst:
        1. If src == dst or flights[src][dst] == 1, update next_dp[dst].
    3. Replace dp with next_dp.
  6. Return max(dp).

Correctness

Before week w, let dp[city] be the maximum vacation days possible after finishing weeks 0 through w - 1 and ending in city.

This is true initially because before any week starts, we are in city 0 with 0 vacation days, and every other city is unreachable.

For each week, the algorithm considers every reachable source city and every valid destination city. A destination is valid exactly when we either stay in the same city or there is a direct flight from the source city to the destination city.

When we choose destination dst for week w, we gain:

days[dst][w]

vacation days. Therefore the transition computes the best possible total after week w.

Since every legal schedule consists of exactly one such stay-or-flight choice per week, every legal schedule is considered. Since the algorithm always keeps the maximum value for each destination city, no worse schedule can affect the answer.

After all weeks are processed, we may end in any city. So the maximum value over all cities is exactly the maximum total vacation days possible.

Complexity

Let n be the number of cities and k be the number of weeks.

Metric Value Why
Time O(k n^2) For each week, we try every source and destination city
Space O(n) We keep only the previous and current week DP arrays

Implementation

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

        NEG_INF = -10**18

        dp = [NEG_INF] * n
        dp[0] = 0

        for week in range(k):
            next_dp = [NEG_INF] * n

            for src in range(n):
                if dp[src] == NEG_INF:
                    continue

                for dst in range(n):
                    if src == dst or flights[src][dst] == 1:
                        next_dp[dst] = max(
                            next_dp[dst],
                            dp[src] + days[dst][week],
                        )

            dp = next_dp

        return max(dp)

Code Explanation

We start with city 0 reachable:

dp[0] = 0

Every other city starts as unreachable:

dp = [NEG_INF] * n

For each week, we create a new DP array:

next_dp = [NEG_INF] * n

Then we try all possible transitions from source city to destination city:

if src == dst or flights[src][dst] == 1:

The condition includes staying in the same city. This is necessary because flights[i][i] is 0, but staying is always allowed.

If the move is valid, we update the best total for the destination:

next_dp[dst] = max(next_dp[dst], dp[src] + days[dst][week])

After all transitions for the week are done, we move forward:

dp = next_dp

Finally, the answer is the best total among all ending cities.

Testing

def run_tests():
    s = Solution()

    assert s.maxVacationDays(
        [
            [0, 1, 1],
            [1, 0, 1],
            [1, 1, 0],
        ],
        [
            [1, 3, 1],
            [6, 0, 3],
            [3, 3, 3],
        ],
    ) == 12

    assert s.maxVacationDays(
        [
            [0, 0, 0],
            [0, 0, 0],
            [0, 0, 0],
        ],
        [
            [1, 1, 1],
            [7, 7, 7],
            [7, 7, 7],
        ],
    ) == 3

    assert s.maxVacationDays(
        [
            [0, 1, 1],
            [1, 0, 1],
            [1, 1, 0],
        ],
        [
            [7, 0, 0],
            [0, 7, 0],
            [0, 0, 7],
        ],
    ) == 21

    assert s.maxVacationDays(
        [[0]],
        [[5, 6, 7]],
    ) == 18

    print("all tests passed")

run_tests()
Test Why
Fully connected sample Checks normal weekly city choices
No flights Must stay in city 0
Best city changes each week Checks flight transitions
One city Only staying is possible