568. Maximum Vacation Days

public class Solution {
    public int MaxVacationDays(int[][] flights, int[][] days) {
        int n = flights.Length, k = days[0].Length;
        int[][] memo = new int[n][];
        for (int i = 0; i < n; i++) {
            memo[i] = new int[k];
            Array.Fill(memo[i], -1);
        }
        return Dfs(flights, days, memo, 0, 0);
    }
    private int Dfs(int[][] flights, int[][] days, int[][] memo, int curCity, int weekNo) {
        int n = flights.Length, k = days[0].Length;
        if (weekNo == k) return 0;
        if (memo[curCity][weekNo] != -1) return memo[curCity][weekNo];
        int maxVac = 0;
        for (int nextCity = 0; nextCity < n; nextCity++) {
            if (curCity == nextCity || flights[curCity][nextCity] == 1) {
                maxVac = Math.Max(maxVac, days[nextCity][weekNo] + Dfs(flights, days, memo, nextCity, weekNo + 1));
            }
        }
        memo[curCity][weekNo] = maxVac;
        return maxVac;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxVacationDays(int[][] flights, int[][] days) {
        int n = flights.size(), k = days[0].size();
        int[][] memo = new int[n][];
        for (int i = 0; i < n; i++) {
            memo[i] = new int[k];
            Array.Fill(memo[i], -1);
        }
        return Dfs(flights, days, memo, 0, 0);
    }
    private int Dfs(int[][] flights, int[][] days, int[][] memo, int curCity, int weekNo) {
        int n = flights.size(), k = days[0].size();
        if (weekNo == k) return 0;
        if (memo[curCity][weekNo] != -1) return memo[curCity][weekNo];
        int maxVac = 0;
        for (int nextCity = 0; nextCity < n; nextCity++) {
            if (curCity == nextCity || flights[curCity][nextCity] == 1) {
                maxVac = max(maxVac, days[nextCity][weekNo] + Dfs(flights, days, memo, nextCity, weekNo + 1));
            }
        }
        memo[curCity][weekNo] = maxVac;
        return maxVac;
    }
}

public class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        int n = flights.length;
        int k = days[0].length;
        int[][] memo = new int[n][k];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(flights, days, memo, 0, 0);
    }
    private int dfs(int[][] flights, int[][] days, int[][] memo, int curCity, int weekNo) {
        int n = flights.length;
        int k = days[0].length;
        if (weekNo == k) return 0;
        if (memo[curCity][weekNo] != -1) return memo[curCity][weekNo];
        int maxVac = 0;
        for (int nextCity = 0; nextCity < n; nextCity++) {
            if (curCity == nextCity || flights[curCity][nextCity] == 1) {
                maxVac = Math.max(maxVac, days[nextCity][weekNo] + dfs(flights, days, memo, nextCity, weekNo + 1));
            }
        }
        memo[curCity][weekNo] = maxVac;
        return maxVac;
    }
}

var maxVacationDays = function(flights, days) {
    const n = flights.length;
    const k = days[0].length;
    const memo = Array.from({ length: n }, () => Array(k).fill(-1));

    const dfs = (curCity, weekNo) => {
        if (weekNo === k) return 0;
        if (memo[curCity][weekNo] !== -1) return memo[curCity][weekNo];
        let maxVac = 0;
        for (let nextCity = 0; nextCity < n; nextCity++) {
            if (curCity === nextCity || flights[curCity][nextCity] === 1) {
                maxVac = Math.max(maxVac, days[nextCity][weekNo] + dfs(nextCity, weekNo + 1));
            }
        }
        memo[curCity][weekNo] = maxVac;
        return maxVac;
    };

    return dfs(0, 0);
};

class Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        n, k = len(flights), len(days[0])
        memo = [[-1] * k for _ in range(n)]

        def dfs(cur_city, weekno):
            if weekno == k:
                return 0
            if memo[cur_city][weekno] != -1:
                return memo[cur_city][weekno]
            max_vac = 0
            for next_city in range(n):
                if cur_city == next_city or flights[cur_city][next_city] == 1:
                    max_vac = max(max_vac, days[next_city][weekno] + dfs(next_city, weekno + 1))
            memo[cur_city][weekno] = max_vac
            return max_vac

        return dfs(0, 0)

func maxVacationDays(flights [][]int, days [][]int) int {
    n, k := len(flights), len(days[0])
    memo := make([][]int, n)
    for i := range memo {
        memo[i] = make([]int, k)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    return dfs(flights, days, memo, 0, 0)
}

func dfs(flights [][]int, days [][]int, memo [][]int, curCity, weekNo int) int {
    n, k := len(flights), len(days[0])
    if weekNo == k {
        return 0
    }
    if memo[curCity][weekNo] != -1 {
        return memo[curCity][weekNo]
    }
    maxVac := 0
    for nextCity := 0; nextCity < n; nextCity++ {
        if curCity == nextCity || flights[curCity][nextCity] == 1 {
            maxVac = max(maxVac, days[nextCity][weekNo]+dfs(flights, days, memo, nextCity, weekNo+1))
        }
    }
    memo[curCity][weekNo] = maxVac
    return maxVac
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Algorithm

Правила и ограничения:

Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник.

Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0.

У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается.

Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j.

Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель.

Пример:

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.

👨‍💻

Алгоритм:

Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i].

Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1).

Для текущего города необходимо найти максимальное количество отпускных дней, выбирая различные города в качестве следующего местоположения. Из всех вариантов отпускных дней выбираем максимальное значение, которое и будет возвращено для каждого вызова функции dfs.

😎