Maximum Vacation Days

Problem

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:

1. You can only travel among n cities, represented by indexes from 0 to n - 1. Initially, you are in the city indexed 0 on Monday.
2. The cities are connected by flights. The flights are represented as an 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.
3. You totally have 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.
4. For each city, you can only have restricted vacation days in different weeks, given an 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.
5. You could stay in a city beyond the number of vacation days, but you should work on the extra days, which will not be counted as vacation days.
6. If you fly from city 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.
7. We do not consider the impact of flight hours on the calculation of vacation days.

Given the two matrices flights and days, return the maximum vacation days you could take duringk weeks.

Examples

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.length
• n == flights[i].length
• n == days.length
• k == days[i].length
• 1 <= n, k <= 100
• flights[i][j] is either 0 or 1.
• 0 <= days[i][j] <= 7

Solution

Method 1 – Dynamic Programming (State by City and Week)

Intuition

To maximize vacation days, we use dynamic programming to track the best possible vacation days for each city and week. For each week, we consider all possible flights and stays, updating the DP table accordingly.

Approach

1. Initialize a DP table dp[city][week] to store the max vacation days for each city and week.
2. Set dp[0][0] = days[0][0] (start in city 0, week 0).
3. For each week from 1 to k-1:
   • For each city, check all possible previous cities that can reach it (by flight or staying).
   • Update dp[city][week] with the max vacation days from previous city plus current week's vacation days.
4. The answer is the maximum value in the last week across all cities.

Complexity

• ⏰ Time complexity: O(n^2 * k) — For each week, check all city pairs.
• 🧺 Space complexity: O(n * k) — For the DP table.

Code

C++

class Solution {
public:
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        int n = flights.size(), k = days[0].size();
        vector<vector<int>> dp(n, vector<int>(k, -1));
        dp[0][0] = days[0][0];
        for (int w = 1; w < k; ++w) {
            for (int c = 0; c < n; ++c) {
                for (int prev = 0; prev < n; ++prev) {
                    if (dp[prev][w-1] != -1 && (flights[prev][c] || prev == c)) {
                        dp[c][w] = max(dp[c][w], dp[prev][w-1] + days[c][w]);
                    }
                }
            }
        }
        return *max_element(dp.begin(), dp.end(), [&](auto& a, auto& b) { return a.back() < b.back(); })->rbegin();
    }
};

Go

func maxVacationDays(flights [][]int, days [][]int) int {
    n, k := len(flights), len(days[0])
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, k)
        for j := range dp[i] { dp[i][j] = -1 }
    }
    dp[0][0] = days[0][0]
    for w := 1; w < k; w++ {
        for c := 0; c < n; c++ {
            for prev := 0; prev < n; prev++ {
                if dp[prev][w-1] != -1 && (flights[prev][c] == 1 || prev == c) {
                    if dp[c][w] < dp[prev][w-1]+days[c][w] {
                        dp[c][w] = dp[prev][w-1]+days[c][w]
                    }
                }
            }
        }
    }
    ans := 0
    for c := 0; c < n; c++ {
        if dp[c][k-1] > ans { ans = dp[c][k-1] }
    }
    return ans
}

Java

class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        int n = flights.length, k = days[0].length;
        int[][] dp = new int[n][k];
        for (int[] row : dp) Arrays.fill(row, -1);
        dp[0][0] = days[0][0];
        for (int w = 1; w < k; ++w) {
            for (int c = 0; c < n; ++c) {
                for (int prev = 0; prev < n; ++prev) {
                    if (dp[prev][w-1] != -1 && (flights[prev][c] == 1 || prev == c)) {
                        dp[c][w] = Math.max(dp[c][w], dp[prev][w-1] + days[c][w]);
                    }
                }
            }
        }
        int ans = 0;
        for (int c = 0; c < n; ++c) ans = Math.max(ans, dp[c][k-1]);
        return ans;
    }
}

Kotlin

class Solution {
    fun maxVacationDays(flights: Array<IntArray>, days: Array<IntArray>): Int {
        val n = flights.size
        val k = days[0].size
        val dp = Array(n) { IntArray(k) { -1 } }
        dp[0][0] = days[0][0]
        for (w in 1 until k) {
            for (c in 0 until n) {
                for (prev in 0 until n) {
                    if (dp[prev][w-1] != -1 && (flights[prev][c] == 1 || prev == c)) {
                        dp[c][w] = maxOf(dp[c][w], dp[prev][w-1] + days[c][w])
                    }
                }
            }
        }
        var ans = 0
        for (c in 0 until n) ans = maxOf(ans, dp[c][k-1])
        return ans
    }
}

Python

def max_vacation_days(flights: list[list[int]], days: list[list[int]]) -> int:
    n, k = len(flights), len(days[0])
    dp = [[-1]*k for _ in range(n)]
    dp[0][0] = days[0][0]
    for w in range(1, k):
        for c in range(n):
            for prev in range(n):
                if dp[prev][w-1] != -1 and (flights[prev][c] or prev == c):
                    dp[c][w] = max(dp[c][w], dp[prev][w-1] + days[c][w])
    return max(dp[c][k-1] for c in range(n))

Rust

impl Solution {
    pub fn max_vacation_days(flights: Vec<Vec<i32>>, days: Vec<Vec<i32>>) -> i32 {
        let n = flights.len();
        let k = days[0].len();
        let mut dp = vec![vec![-1; k]; n];
        dp[0][0] = days[0][0];
        for w in 1..k {
            for c in 0..n {
                for prev in 0..n {
                    if dp[prev][w-1] != -1 && (flights[prev][c] == 1 || prev == c) {
                        dp[c][w] = dp[c][w].max(dp[prev][w-1] + days[c][w]);
                    }
                }
            }
        }
        (0..n).map(|c| dp[c][k-1]).max().unwrap()
    }
}

TypeScript

class Solution {
    maxVacationDays(flights: number[][], days: number[][]): number {
        const n = flights.length, k = days[0].length;
        const dp = Array.from({length: n}, () => Array(k).fill(-1));
        dp[0][0] = days[0][0];
        for (let w = 1; w < k; ++w) {
            for (let c = 0; c < n; ++c) {
                for (let prev = 0; prev < n; ++prev) {
                    if (dp[prev][w-1] !== -1 && (flights[prev][c] || prev === c)) {
                        dp[c][w] = Math.max(dp[c][w], dp[prev][w-1] + days[c][w]);
                    }
                }
            }
        }
        let ans = 0;
        for (let c = 0; c < n; ++c) ans = Math.max(ans, dp[c][k-1]);
        return ans;
    }
}