# LeetCode 568: Maximum Vacation Days

## 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:

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

## Examples

Example 1:

```python
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:

```python
6 + 3 + 3 = 12
```

So the answer is:

```python
12
```

Example 2:

```python
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:

```python
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:

```python
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:

```python
src == dst
```

or:

```python
flights[src][dst] == 1
```

Then we can update:

```python
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:
   ```python id="fd91o4"
   dp = [-inf] * n
   ```
4. Set:
   ```python id="kbbtit"
   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:

```python
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

```python
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:

```python
dp[0] = 0
```

Every other city starts as unreachable:

```python
dp = [NEG_INF] * n
```

For each week, we create a new DP array:

```python
next_dp = [NEG_INF] * n
```

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

```python
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:

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

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

```python
dp = next_dp
```

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

## Testing

```python
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 |