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:
n cities, represented by indexes from 0 to n - 1. Initially, you are in the city indexed 0 on Monday.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.k weeks (each week has seven days) to travel. You can only take flights at most once per day and can only take flights on each week's Monday morning. Since flight time is so short, we do not consider the impact of flight time.n x k matrix called days representing this relationship. For the value of days[i][j], it represents the maximum days you could take a vacation in the city i in the week j.A to city B and take the vacation on that day, the deduction towards vacation days will count towards the vacation days of city B in that week.Given the two matrices flights and days, return the maximum vacation days you could take during 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 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. (Although you start at city 0, we could also fly to and start at other cities since it is Monday.) 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 to play and six days to work. So the maximum number of vacation days is 3. Ans = 1 + 1 + 1 = 3.
Example 3:
Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[7,0,0],[0,7,0],[0,0,7]] Output: 21 Explanation: One of the best strategies is: 1st week : stay at city 0, and play 7 days. 2nd week : fly from city 0 to city 1 on Monday, and play 7 days. 3rd week : fly from city 1 to city 2 on Monday, and play 7 days. Ans = 7 + 7 + 7 = 21
Constraints:
n == flights.lengthn == flights[i].lengthn == days.lengthk == days[i].length1 <= n, k <= 100flights[i][j] is either 0 or 1.0 <= days[i][j] <= 7Problem Overview: You start in city 0 and have k weeks to travel across n cities. A flight matrix tells you which cities are connected, and a vacation matrix tells how many days you can spend in each city per week. Each Monday you can stay or take a flight, and the goal is to maximize total vacation days.
Approach 1: DFS + Memoization (Top-Down DP) (Time: O(k * n^2), Space: O(k * n))
This approach models the problem as a decision tree: for every week and city, you choose whether to stay or fly to another reachable city. A recursive DFS explores all possible paths across weeks. Without optimization this becomes exponential, but memoization caches results for states defined by (week, city). Each state iterates through all cities to check valid flights using the adjacency matrix, accumulating the best possible vacation total. Memoization ensures each state is computed once, reducing the complexity to O(k * n^2). This version is intuitive and mirrors the natural decision process of the problem.
Approach 2: Bottom-Up Dynamic Programming (Matrix Transition) (Time: O(k * n^2), Space: O(n))
The iterative DP approach builds results week by week. Define dp[c] as the maximum vacation days achievable when starting the current week in city c. For each week, compute a new array by considering transitions from every previous city. If you can stay or fly (flights[prev][curr] == 1), update the best value using dp[prev] + days[curr][week]. This essentially treats the flight matrix as a transition graph and the vacation matrix as weekly rewards. Rolling arrays reduce memory to O(n). This approach avoids recursion and runs efficiently even when the number of weeks is large.
The key insight is that every week represents a layer in the state graph, and cities are nodes in that layer. Transitions come from the flight matrix, while rewards come from the vacation matrix. Dynamic programming works well because optimal choices for future weeks depend only on the current week and city.
Understanding matrix-based transitions is common in problems involving travel schedules or stage-based decisions. Related patterns appear in dynamic programming, grid-like reasoning with matrix data, and iteration over array structures.
Recommended for interviews: The bottom-up dynamic programming approach is what interviewers typically expect. It clearly shows you can model the problem as states and transitions. Explaining the DFS version first demonstrates problem understanding, while implementing the iterative DP proves you can optimize time and space.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS + Memoization | O(k * n^2) | O(k * n) | Good for understanding the decision tree and converting brute force recursion into DP |
| Bottom-Up Dynamic Programming | O(k * n^2) | O(n) | Best practical solution; efficient and commonly expected in interviews |
LeetCode 568. Maximum Vacation Days • Happy Coding • 3,331 views views
Watch 4 more video solutions →Practice Maximum Vacation Days with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor