0568. 最大休假天数

ITCharge大约 4 分钟

---

0568. 最大休假天数

标签：数组、动态规划、矩阵
难度：困难

题目链接

0568. 最大休假天数 - 力扣

题目大意

描述：

LeetCode 想让一个最优秀的员工在 $N$ 个城市中旅行 $K$ 周。员工的工作就是安排旅行使得最大化可以休假的天数，但是需要遵守一些规则和限制。

规则和限制：

只能在 $N$ 个城市之间旅行，城市用 $0 \sim n - 1$ 的索引表示。一开始，员工位于索引 0 的城市，并且那天是星期一。
城市之间通过航班相连，这些航班用一个 $n \times n$ 的矩阵 $flights$ 表示， $flights[i][j] = 1$ 表示城市 $i$ 和城市 $j$ 之间有航班（ $i = j$ 表示可以留在当前城市）。
员工总共有 $K$ 周（每周 7 天）的时间旅行，每天最多只能乘坐一次航班，并且只能在每周一上午乘坐航班（不需要考虑飞行时间的影响）。
每个城市的休假天数是不一样的，给定 $N \times K$ 的矩阵 $days$ ， $days[i][j]$ 表示在第 $j$ 周在城市 $i$ 可以休假的最长天数。
如果您从 A 市飞往 B 市，并在当天休假，扣除的假期天数将计入 B 市当周的休假天数。
我们不考虑飞行时数对休假天数计算的影响。

员工从城市 $0$ 开始，每周必须选择一个可以到达的城市（包括当前城市）。

要求：

返回员工在 $K$ 周内最多可以休假的天数。

说明：

$N$ 和 $K$ 都是正整数，范围在 $[1, 100]$ 内。
$flights$ 矩阵的大小为 $N \times N$ 。
$days$ 矩阵的大小为 $N \times K$ 。
$0 \le days[i][j] \le 7$ 。

示例：

示例 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.

解题思路

思路 1：动态规划

定义 $dp[week][city]$ 表示在第 $week$ 周结束时位于城市 $city$ 能获得的最大休假天数。

状态转移：

对于第 $week$ 周，如果要在城市 $j$ 度过，需要从某个城市 $i$ 飞过来（或留在原地）
$dp[week][j] = \max(dp[week-1][i] + days[j][week])$ ，其中 $flights[i][j] = 1$

初始状态： $dp[0][0] = days[0][0]$ ，以及所有从城市 $0$ 可以直达的城市。

思路 1：代码

class Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        n = len(flights)  # 城市数量
        k = len(days[0])  # 周数
        
        # dp[week][city] 表示第 week 周在 city 城市的最大休假天数
        dp = [[-1] * n for _ in range(k)]
        
        # 初始化第 0 周
        dp[0][0] = days[0][0]
        for j in range(n):
            if flights[0][j] == 1:
                dp[0][j] = days[j][0]
        
        # 动态规划
        for week in range(1, k):
            for j in range(n):
                # 尝试从每个城市 i 到达城市 j
                for i in range(n):
                    if dp[week-1][i] != -1 and (i == j or flights[i][j] == 1):
                        dp[week][j] = max(dp[week][j], dp[week-1][i] + days[j][week])
        
        # 返回最后一周的最大值
        return max(dp[k-1])

思路 1：复杂度分析

时间复杂度： $O(K \times N^2)$ ，其中 $K$ 是周数， $N$ 是城市数量。需要遍历每周每个城市的每个来源城市。
空间复杂度： $O(K \times N)$ ，需要存储 $dp$ 数组。可以优化到 $O(N)$ 使用滚动数组。