568. 最大休假天数 🔒

题目描述

力扣想让一个最优秀的员工在 N 个城市间旅行来收集算法问题。但只工作不玩耍，聪明的孩子也会变傻，所以您可以在某些特定的城市和星期休假。您的工作就是安排旅行使得最大化你可以休假的天数，但是您需要遵守一些规则和限制。

规则和限制：

您只能在 N 个城市之间旅行，用 0 到 n-1 的索引表示。一开始，您在索引为 0 的城市，并且那天是星期一。
这些城市通过航班相连。这些航班用 n x n 矩阵 flights（不一定是对称的）表示，flights[i][j] 代表城市 i 到城市 j 的航空状态。如果没有城市 i 到城市 j 的航班，flights[i][j] = 0 ；否则，flights[i][j] = 1 。同时，对于所有的 i ，flights[i][i] = 0 。
您总共有 k 周（每周7天）的时间旅行。您每天最多只能乘坐一次航班，并且只能在每周的星期一上午乘坐航班。由于飞行时间很短，我们不考虑飞行时间的影响。
对于每个城市，不同的星期您休假天数是不同的，给定一个 N*K 矩阵 days 代表这种限制，days[i][j] 代表您在第j个星期在城市i能休假的最长天数。
如果您从 A 市飞往 B 市，并在当天休假，扣除的假期天数将计入 B 市当周的休假天数。
我们不考虑飞行时数对休假天数计算的影响。

给定 flights 矩阵和 days 矩阵，您需要输出 k 周内可以休假的最长天数。

示例 1:

输入:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
输出: 12
解释: 
最好的策略之一：
第一个星期 : 星期一从城市 0 飞到城市 1，玩 6 天，工作 1 天。 
（虽然你是从城市 0 开始，但因为是星期一，我们也可以飞到其他城市。） 
第二个星期 : 星期一从城市 1 飞到城市 2，玩 3 天，工作 4 天。
第三个星期 : 呆在城市 2，玩 3 天，工作 4 天。
Ans = 6 + 3 + 3 = 12.

示例 2:

输入:flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[7,7,7]]
输出: 3
解释: 
由于没有航班可以让您飞到其他城市，你必须在城市 0 呆整整 3 个星期。 
对于每一个星期，你只有一天时间玩，剩下六天都要工作。 
所以最大休假天数为 3.
Ans = 1 + 1 + 1 = 3.

示例 3:

输入:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[7,0,0],[0,7,0],[0,0,7]]
输出: 21
解释:
最好的策略之一是：
第一个星期 : 呆在城市 0，玩 7 天。 
第二个星期 : 星期一从城市 0 飞到城市 1，玩 7 天。
第三个星期 : 星期一从城市 1 飞到城市 2，玩 7 天。
Ans = 7 + 7 + 7 = 21

提示:

n == flights.length
n == flights[i].length
n == days.length
k == days[i].length
1 <= n, k <= 100
flights[i][j] 不是 0 就是 1
0 <= days[i] <= 7

解法

方法一：动态规划

我们定义 \(f[k][j]\) 表示前 \(k\) 周，且最后一周在城市 \(j\) 休假的最长天数。初始时 \(f[0][0]=0\)，其它 \(f[0][j]=-\infty\)。答案为 \(\max_{j=0}^{n-1} f[K][j]\)。

接下来，我们考虑如何计算 \(f[k][j]\)。对于当前这一周，我们可以枚举上一周所在的城市 \(i\)，城市 \(i\) 可以和城市 \(j\) 相等，那么 \(f[k][j] = f[k-1][i]\)；也可以和城市 \(j\) 不相等，如果不相等，我们需要判断是否可以从城市 \(i\) 飞到城市 \(j\)，如果可以，那么 \(f[k][j] = \max(f[k][j], f[k-1][i])\)。最后，我们还需要加上这一周在城市 \(j\) 休假的天数 \(\textit{days}[j][k-1]\)。

最终的答案即为 \(\max_{j=0}^{n-1} f[K][j]\)。

时间复杂度 \(O(K \times n^2)\)，空间复杂度 \(O(K \times n)\)。其中 \(K\) 和 \(n\) 分别为周数和城市数。

Python3JavaC++GoTypeScriptRust

class Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        n = len(flights)
        K = len(days[0])
        f = [[-inf] * n for _ in range(K + 1)]
        f[0][0] = 0
        for k in range(1, K + 1):
            for j in range(n):
                f[k][j] = f[k - 1][j]
                for i in range(n):
                    if flights[i][j]:
                        f[k][j] = max(f[k][j], f[k - 1][i])
                f[k][j] += days[j][k - 1]
        return max(f[-1][j] for j in range(n))

class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        int n = flights.length;
        int K = days[0].length;
        final int inf = 1 << 30;
        int[][] f = new int[K + 1][n];
        for (var g : f) {
            Arrays.fill(g, -inf);
        }
        f[0][0] = 0;
        for (int k = 1; k <= K; ++k) {
            for (int j = 0; j < n; ++j) {
                f[k][j] = f[k - 1][j];
                for (int i = 0; i < n; ++i) {
                    if (flights[i][j] == 1) {
                        f[k][j] = Math.max(f[k][j], f[k - 1][i]);
                    }
                }
                f[k][j] += days[j][k - 1];
            }
        }
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            ans = Math.max(ans, f[K][j]);
        }
        return ans;
    }
}

class Solution {
public:
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        int n = flights.size();
        int K = days[0].size();
        int f[K + 1][n];
        memset(f, -0x3f, sizeof(f));
        f[0][0] = 0;
        for (int k = 1; k <= K; ++k) {
            for (int j = 0; j < n; ++j) {
                f[k][j] = f[k - 1][j];
                for (int i = 0; i < n; ++i) {
                    if (flights[i][j] == 1) {
                        f[k][j] = max(f[k][j], f[k - 1][i]);
                    }
                }
                f[k][j] += days[j][k - 1];
            }
        }
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            ans = max(ans, f[K][j]);
        }
        return ans;
    }
};

func maxVacationDays(flights [][]int, days [][]int) (ans int) {
    n, K := len(flights), len(days[0])
    f := make([][]int, K+1)
    for i := range f {
        f[i] = make([]int, n)
        for j := range f[i] {
            f[i][j] = -(1 << 30)
        }
    }
    f[0][0] = 0
    for k := 1; k <= K; k++ {
        for j := 0; j < n; j++ {
            f[k][j] = f[k-1][j]
            for i := 0; i < n; i++ {
                if flights[i][j] == 1 {
                    f[k][j] = max(f[k][j], f[k-1][i])
                }
            }
            f[k][j] += days[j][k-1]
        }
    }
    for j := 0; j < n; j++ {
        ans = max(ans, f[K][j])
    }
    return
}

function maxVacationDays(flights: number[][], days: number[][]): number {
    const n = flights.length;
    const K = days[0].length;
    const inf = Number.NEGATIVE_INFINITY;
    const f: number[][] = Array.from({ length: K + 1 }, () => Array(n).fill(inf));
    f[0][0] = 0;
    for (let k = 1; k <= K; k++) {
        for (let j = 0; j < n; j++) {
            f[k][j] = f[k - 1][j];
            for (let i = 0; i < n; i++) {
                if (flights[i][j]) {
                    f[k][j] = Math.max(f[k][j], f[k - 1][i]);
                }
            }
            f[k][j] += days[j][k - 1];
        }
    }
    return Math.max(...f[K]);
}

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 inf = i32::MIN;

        let mut f = vec![vec![inf; n]; k + 1];
        f[0][0] = 0;

        for step in 1..=k {
            for j in 0..n {
                f[step][j] = f[step - 1][j];
                for i in 0..n {
                    if flights[i][j] == 1 {
                        f[step][j] = f[step][j].max(f[step - 1][i]);
                    }
                }
                f[step][j] += days[j][step - 1];
            }
        }

        *f[k].iter().max().unwrap()
    }
}

568. 最大休假天数 🔒

题目描述

解法

方法一：动态规划

评论