Problem Description

You are given two matrices: flights and days.

• flights[i][j] == 1 means there is a direct flight from city i to city j. You can always stay in the same city (think of flights[i][i] == 1 for all i).
• days[i][w] represents the maximum vacation days you can spend in city i during week w.

• You can only take one flight per week (at the start of the week).
• You must always be in some city each week.
• You may not be able to reach every city from city 0.
• Input sizes: flights and days are both n x k matrices, where n is the number of cities and k is the number of weeks.

Find the maximum total vacation days you can take.

Thought Process

At first glance, this problem looks like a pathfinding or scheduling problem, where each week you can choose to stay or travel, and you want to maximize your reward (vacation days). A brute-force approach would be to try every possible path: for each week, for each city, try all reachable cities and calculate the total days.

However, with up to 100 cities and 100 weeks, the number of possible paths grows exponentially. This makes brute-force infeasible.

We need to optimize by realizing that the state at each week is simply: "Which city am I in, and what week is it?" For each state, we only care about the best possible total vacation days we could have accumulated up to that point. This is a classic setup for Dynamic Programming (DP).

We can use a DP table where dp[week][city] represents the maximum vacation days we can have if we are in city at the start of week. We build up this table week by week, considering all possible transitions (flights or staying put).

Solution Approach

Let's break down the solution step by step:

1. Initialization:
   • Set up a DP table: dp[city] for the current week, and next_dp[city] for the next week.
   • At week 0, we can only be in city 0, so set dp[0] = days[0][0]; all other cities start as unreachable (e.g., -inf).
2. Iterate over weeks:
   • For each week, for each city i, if dp[i] is reachable, consider all cities j you can fly to (including staying in i).
   • For each such j, update next_dp[j] as the max of its current value and dp[i] + days[j][week].
3. Transition:
   • After processing all cities for a week, set dp = next_dp and continue to the next week.
4. Result:
   • After the last week, the answer is the maximum value in dp (the best vacation days possible in any city at the end).

This approach ensures we only process each state once per week, making the solution efficient.

Example Walkthrough

Let's consider the following example:
Input:
flights = [[0,1,1],[1,0,1],[1,1,0]]
days = [[1,3,1],[6,0,3],[3,3,3]]

Explanation:

• There are 3 cities and 3 weeks.
• You start in city 0. Let's build the DP table week by week.

1. Week 0:
   • Can only be in city 0: dp = [1, -inf, -inf] (since days[0][0] = 1).
2. Week 1:
   • From city 0, can fly to city 1 or 2 (since flights[0][1] == 1 and flights[0][2] == 1), or stay in city 0.
   • For city 0: 1 + days[0][1] = 1 + 3 = 4
   • For city 1: 1 + days[1][1] = 1 + 0 = 1
   • For city 2: 1 + days[2][1] = 1 + 3 = 4
   • dp = [4, 1, 4]
3. Week 2:
   • Repeat for each city you could be in at week 1:
   • From city 0 (dp=4): can go to 0, 1, 2.
     • To 0: 4+1=5
     • To 1: 4+3=7
     • To 2: 4+3=7
   • From city 1 (dp=1): can go to 0, 1, 2.
     • To 0: 1+1=2
     • To 1: 1+3=4
     • To 2: 1+3=4
   • From city 2 (dp=4): can go to 0, 1, 2.
     • To 0: 4+1=5
     • To 1: 4+3=7
     • To 2: 4+3=7
   • Take the max for each city: dp = [5, 7, 7]

Time and Space Complexity

Brute-force:

• For each week, you could try every possible city, for every possible previous city, leading to exponential time: O(n^k) where n is the number of cities and k is the number of weeks.

• For each week (k), for each city (n), for each possible previous city (n), we do a constant amount of work.
• So, total time complexity: O(k * n^2).
• Space complexity: O(n) if we only keep two arrays for current and next week; O(k * n) if we keep the full DP table.

This is efficient enough for the problem constraints.

Summary

The Maximum Vacation Days problem is a great example of optimizing a path-finding problem with dynamic programming. By modeling the problem as a series of states (city, week), and only keeping track of the best possible vacation days for each state, we avoid the exponential explosion of brute-force. The DP approach is both efficient and elegant, and can be implemented with a simple nested loop structure.

Code Implementation

class Solution:
    def maxVacationDays(self, flights, days):
        n = len(flights)
        k = len(days[0])
        dp = [-float('inf')] * n
        dp[0] = 0
        for week in range(k):
            next_dp = [-float('inf')] * n
            for i in range(n):
                if dp[i] == -float('inf'):
                    continue
                for j in range(n):
                    if i == j or flights[i][j]:
                        next_dp[j] = max(next_dp[j], dp[i] + days[j][week])
            dp = next_dp
        return max(dp)
      

class Solution {
public:
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        int n = flights.size(), k = days[0].size();
        vector<int> dp(n, INT_MIN);
        dp[0] = 0;
        for (int week = 0; week < k; ++week) {
            vector<int> next_dp(n, INT_MIN);
            for (int i = 0; i < n; ++i) {
                if (dp[i] == INT_MIN) continue;
                for (int j = 0; j < n; ++j) {
                    if (i == j || flights[i][j]) {
                        next_dp[j] = max(next_dp[j], dp[i] + days[j][week]);
                    }
                }
            }
            dp = next_dp;
        }
        return *max_element(dp.begin(), dp.end());
    }
};
      

class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        int n = flights.length, k = days[0].length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = 0;
        for (int week = 0; week < k; ++week) {
            int[] next_dp = new int[n];
            Arrays.fill(next_dp, Integer.MIN_VALUE);
            for (int i = 0; i < n; ++i) {
                if (dp[i] == Integer.MIN_VALUE) continue;
                for (int j = 0; j < n; ++j) {
                    if (i == j || flights[i][j] == 1) {
                        next_dp[j] = Math.max(next_dp[j], dp[i] + days[j][week]);
                    }
                }
            }
            dp = next_dp;
        }
        int res = 0;
        for (int val : dp) res = Math.max(res, val);
        return res;
    }
}
      

var maxVacationDays = function(flights, days) {
    const n = flights.length, k = days[0].length;
    let dp = new Array(n).fill(-Infinity);
    dp[0] = 0;
    for (let week = 0; week < k; ++week) {
        let next_dp = new Array(n).fill(-Infinity);
        for (let i = 0; i < n; ++i) {
            if (dp[i] === -Infinity) continue;
            for (let j = 0; j < n; ++j) {
                if (i === j || flights[i][j]) {
                    next_dp[j] = Math.max(next_dp[j], dp[i] + days[j][week]);
                }
            }
        }
        dp = next_dp;
    }
    return Math.max(...dp);
};