HardArrayDynamic ProgrammingMatrix

Maximum Vacation Days

1 approach, code in every language

There are n cities and k weeks of vacation to plan. A matrix flights of size n x n describes travel: flights[i][j] = 1 means you may fly from city i to city j, and staying put in the same city is always allowed (treat i -> i as permitted regardless of the flights entry).

A second matrix days of size n x k tells you how many vacation days you can take: days[i][w] is the number of days available in city i during week w, capped by that city's rules. On the first day of each week you may either stay or take one flight to another reachable city, and you spend the remainder of that week in whichever city you land in.

You begin in city 0 at the start of week 0. Return the maximum total vacation days you can accumulate across all k weeks.

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

Week 0 fly to city 1 (6 days), week 1 fly to city 2 (3 days), week 2 fly to city 1 (3 days): 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

No flights exist, so you are stuck in city 0 the whole time, collecting 1 + 1 + 1 = 3 days.

Constraints

n == flights.length == 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

DP over Weeks and Cities

Track the best total vacation ending in each city after each week, transitioning only along legal flights or by staying.

Loading animation…

Intuition

The only state that matters at the start of a week is which city you are in, since future choices do not depend on how you arrived. Let dp[city] be the best cumulative vacation total achievable when you spend the current week in that city. To spend a week in city, you must have been in some prior city p last week from which p == city (you stayed) or flights[p][city] == 1 (you flew in). We roll the state forward week by week, adding days[city][w] to the best reachable predecessor. Unreachable cities are marked with a large negative sentinel so they never win a maximization. The answer is the best value across all cities after the final week.

Algorithm walkthrough

1Initialize dp so only the starting city 0 is reachable (dp[0] = 0) and all other cities hold a negative sentinel.
2For each week w, create a fresh ndp array filled with the sentinel.
3For every target city, scan all predecessors p; skip unreachable ones (dp[p] is the sentinel).
4If p == city or flights[p][city] == 1, relax ndp[city] with dp[p] + days[city][w].
5Replace dp with ndp after the week; once all k weeks are done, return the maximum entry of dp.

Implementation

class Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        n = len(flights)
        k = len(days[0]) if n > 0 else 0
        if k == 0:
            return 0
        NEG = float('-inf')
        dp = [NEG] * n
        dp[0] = 0
        for w in range(k):
            ndp = [NEG] * n
            for city in range(n):
                for p in range(n):
                    if dp[p] == NEG:
                        continue
                    if p == city or flights[p][city] == 1:
                        cand = dp[p] + days[city][w]
                        if cand > ndp[city]:
                            ndp[city] = cand
            dp = ndp
        return max(dp)

Time

O(k * n^2)

Space

O(n)

For each of k weeks we relax every (city, predecessor) pair, which is n^2 work; two rolling arrays of size n suffice.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free