Maximum Vacation Days

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

1. 1Initialize dp so only the starting city 0 is reachable (dp[0] = 0) and all other cities hold a negative sentinel.
2. 2For each week w, create a fresh ndp array filled with the sentinel.
3. 3For every target city, scan all predecessors p; skip unreachable ones (dp[p] is the sentinel).
4. 4If p == city or flights[p][city] == 1, relax ndp[city] with dp[p] + days[city][w].
5. 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)