LeetCode 568. 最大休假天数

2025-06-15 HGNULB 约 11 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 568. 最大休假天数

题意分析

有 n 个城市和 k 周假期。flights[i][j] == 1 表示存在从城市 i 飞往城市 j 的航班，days[i][j] 表示在第 j 周待在城市 i 最多能休息多少天。每周的周一早上可以选择飞一次（只能飞一次、只能在周一飞），也可以留在原地；这一整周就算在落地的那个城市，收获对应的休假天数。起点固定是城市 0，问 k 周下来最多能休多少天。

把规则翻译成结构：每周做一次决策，决策的内容是「下周待在哪个城市」，收益由「待在哪」和「第几周」共同决定。这是一条时间轴上的链式决策，每一步的可选范围由当前所在城市的航班决定。

几处必须读准的细节。第一，飞行发生在周初，所以这一周的天数按目的地算，不是按出发地算——把它算成出发地会让整条时间线错开一周。第二，「留在原地」永远是合法的，即使 flights[i][i] 被规定为 0，也不代表不能待着不动。第三，起点城市 0 是硬性规定的，第一周的可选目的地只有城市 0 本身和它能直飞的城市。

关键的算法信号是：未来的收益只取决于「现在是第几周」和「现在人在哪个城市」，跟之前是怎么飞过来的完全无关。既然历史路径可以被彻底忘掉，就说明状态空间只有「周 × 城市」这么大，指数级的路径枚举可以塌缩成多项式递推。

约束方面，城市数与周数都是百级，$O(k \cdot n^2)$ 约在百万量级，完全可以接受；这也解释了为什么可以放心地在每周枚举「所有出发城市 × 所有目的城市」这一对。

边界：某些城市可能在某一周根本到不了（航班图不连通），这些状态必须被标成不可达，绝不能当成「休息 0 天」参与后续转移；days 里的天数非负，所以最终答案至少是 0。

解法：按周滚动动态规划

核心思路

暴力做法是从城市 0 出发做深搜：每周枚举所有可飞的目的地，递归到下一周。分支因子最坏是 n，深度是 k，总共 $n^k$ 条路径，n 和 k 稍大就完全不可行。

但搜索树上有大量重复：两条不同的飞行路线，只要在同一周末停在同一个城市，它们后续能拿到的最大天数就是完全一样的。既然如此，同一个「(周, 城市)」二元组没必要被反复展开——把它算一次记下来即可。这一步观察把 $n^k$ 压成了 $k \cdot n$ 个状态。

状态定义要精确：dp[week][city] = 前 week + 1 周已经休完、且第 week 周人在 city 时，累计能获得的最大休假天数。注意这个量包含第 week 周在 city 拿到的 days[city][week]，「已结算到本周末」这个口径必须全程一致。

转移写成从上一周推到本周：

dp[week][to] = max over from ( dp[week-1][from] ) + days[to][week]，其中 from 需满足 from == to（留在原地）或 flights[from][to] == 1（有直飞航班）。

初始状态是「第 0 周开始前」：人在城市 0、累计 0 天，其余城市不可达。因为合法累计天数始终非负，可以直接用 -1 表示不可达：dp[0] = 0，其余为 -1。这样首周与后续周使用同一套转移。

不可达不能用 0，因为 0 本身是合法收益；否则无法到达的城市会被当作一条真实路线继续转移。-1 与所有合法值严格区分，转移前遇到它直接跳过，也没有极值哨兵参与加法的溢出风险。

由于 dp[week] 只依赖 dp[week-1]，第一维可以整个丢掉，用两个一维数组滚动，空间从 $O(k \cdot n)$ 降到 $O(n)$。

循环不变量：每周开始时，dp[city] 是截至上一周末停在该城市的最大累计天数，不可达时为 -1。枚举所有合法来源后，next[to] 就覆盖了本周能到达 to 的全部路线并保留最大值，因此不变量推进一周。

解题步骤

取 cityCount = flights.length、weekCount = days[0].length。为什么：flights 是 n × n 的邻接矩阵，行数即城市数；周数只能从 days 的列数读出，因为 flights 不含时间信息。

准备 dp 数组，全部填 -1，再令 dp[0] = 0：假期开始前只有城市 0 可达。

每周新建并填充 -1 的 next：本周结果不能覆盖上一周状态，否则一次迭代可能连续飞多次。

枚举出发城市，dp[from] == -1 时跳过：不存在的路线不能产生后继。

再枚举目的城市 to，当 from == to || flights[from][to] == 1 时更新 next[to] = max(next[to], dp[from] + days[to][week])。为什么：from == to 单独写出来是因为题目规定 flights[i][i] == 0，但「留在原地」始终合法，靠矩阵判断会把这个选项弄丢；加的是 days[to][week] 而不是 days[from][week]，因为飞行在周初完成，整周都算在目的地；用 max 是因为同一个 to 可能被多个 from 到达，要保留最优来源。

本周结束后把 dp 指向 next。为什么：滚动到下一轮；直接换引用是 $O(1)$，不需要拷贝。

处理完全部周后，返回 dp 的最大值：终点城市没有限制；答案从 0 开始取最大，也会忽略值为 -1 的不可达状态。

以 flights = [[0,1,1],[1,0,1],[1,1,0]]、days = [[1,3,1],[6,0,3],[3,3,3]] 走一遍（3 个城市、3 周，答案是 12）。

初始：dp = [0, -1, -1]。

第 0 周：只有 from = 0 可用。to = 0 满足 from == to，next[0] = 0 + days[0][0] = 1；to = 1 有航班，next[1] = 0 + days[1][0] = 6；to = 2 有航班，next[2] = 0 + days[2][0] = 3。得 dp = [1, 6, 3]。

第 1 周：from = 0（值 1）可去 0（留下）得 1 + days[0][1] = 1 + 3 = 4、去 1 得 1 + days[1][1] = 1 + 0 = 1、去 2 得 1 + days[2][1] = 1 + 3 = 4。from = 1（值 6）可去 0 得 6 + 3 = 9、留在 1 得 6 + 0 = 6、去 2 得 6 + 3 = 9。from = 2（值 3）可去 0 得 3 + 3 = 6、去 1 得 3 + 0 = 3、留在 2 得 3 + 3 = 6。逐位取最大得 dp = [9, 6, 9]。

第 2 周：from = 0（值 9）→ to = 0 得 9 + days[0][2] = 9 + 1 = 10，to = 1 得 9 + 3 = 12，to = 2 得 9 + 3 = 12。from = 1（值 6）→ to = 0 得 6 + 1 = 7，to = 1 得 6 + 3 = 9，to = 2 得 6 + 3 = 9。from = 2（值 9）→ to = 0 得 9 + 1 = 10，to = 1 得 9 + 3 = 12，to = 2 得 9 + 3 = 12。取最大得 dp = [10, 12, 12]。

返回最大值 12，对应路线「第 0 周飞到城市 1 休 6 天 → 第 1 周飞回城市 0 休 3 天 → 第 2 周飞到城市 1 休 3 天」。这里能看出两个要点：第 0 周的 6 是按目的地城市 1 计的（若按出发地城市 0 计只有 1 天）；第 1 周的 dp[0] = 9 来自 from = 1 而不是留在原地，说明「同一个目的地取所有来源的最大值」这一步确实在起作用。

代码实现

import java.util.Arrays;

class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        int cityCount = flights.length;
        int weekCount = days[0].length;
        int[] dp = new int[cityCount];
        Arrays.fill(dp, -1);
        // 假期开始前：人在城市 0，已休 0 天，其余城市不可达。
        dp[0] = 0;

        for (int week = 0; week < weekCount; week++) {
            // 新开数组，避免本周结果被当作上周状态二次转移。
            int[] next = new int[cityCount];
            Arrays.fill(next, -1);
            for (int from = 0; from < cityCount; from++) {
                if (dp[from] == -1) {
                    continue;
                }
                for (int to = 0; to < cityCount; to++) {
                    // from == to 必须单独判：题目规定 flights[i][i] == 0，但留在原地合法。
                    if (from == to || flights[from][to] == 1) {
                        // 飞行在周初完成，整周算在目的地。
                        next[to] = Math.max(next[to], dp[from] + days[to][week]);
                    }
                }
            }
            dp = next;
        }

        // 最后停在哪个城市无所谓；初值 0 会忽略值为 -1 的不可达城市。
        int answer = 0;
        for (int val : dp) {
            answer = Math.max(answer, val);
        }
        return answer;
    }
}

func maxVacationDays(flights [][]int, days [][]int) int {
	cityCount := len(flights)
	weekCount := len(days[0])

	dp := make([]int, cityCount)
	for i := range dp {
		dp[i] = -1
	}
	// 假期开始前：人在城市 0，已休 0 天，其余城市不可达。
	dp[0] = 0

	for week := 0; week < weekCount; week++ {
		// 新开数组，避免本周结果被当作上周状态二次转移。
		next := make([]int, cityCount)
		for i := range next {
			next[i] = -1
		}

		for from := 0; from < cityCount; from++ {
			if dp[from] == -1 {
				continue
			}
			for to := 0; to < cityCount; to++ {
				// from == to 必须单独判：题目规定 flights[i][i] == 0，但留在原地合法。
				if from == to || flights[from][to] == 1 {
					// 飞行在周初完成，整周算在目的地。
					val := dp[from] + days[to][week]
					if val > next[to] {
						next[to] = val
					}
				}
			}
		}

		dp = next
	}

	// 最后停在哪个城市无所谓；初值 0 会忽略值为 -1 的不可达城市。
	answer := 0
	for _, val := range dp {
		if val > answer {
			answer = val
		}
	}

	return answer
}

复杂度分析

时间复杂度：$O(k \cdot n^2)$，k 为周数、n 为城市数。凭什么：外层跑 k 周，每周要枚举「出发城市 × 目的城市」共 $n^2$ 对，每对只做一次判断、一次加法和一次取最大，全是常数操作；不可达城市的 continue 只会让实际运行更快，不改变上界。

空间复杂度：$O(n)$。凭什么：任意时刻只同时存在 dp 与 next 两个长度为 n 的数组，第一维（周）被滚动掉了；若保留完整的二维表则是 $O(k \cdot n)$，但由于每周只依赖前一周，没有必要。输入的 flights 与 days 是给定数据，不计入辅助空间。

关键点总结

识别「无后效性」是把指数搜索降成 DP 的第一步：本题里未来收益只依赖「第几周 + 在哪个城市」，历史路径可以整个扔掉，状态空间随之从 $n^k$ 塌缩成 $k \cdot n$。面试时先把这句话说出来。

状态定义必须钉死结算口径。dp[week][city] 到底含不含本周的天数，只要中途摇摆一次，整条时间线就会错开一周。写在白板上、并在转移里逐项对照，是避免这类错误的唯一办法。

收益归属于目的地而非出发地，源于「周初飞行」这个设定。凡是涉及时间轴上的移动，都要先确认「移动发生在计费之前还是之后」。

合法收益非负，因此 -1 是最简单且安全的不可达标记；0 不能用，因为它是合法累计收益。

分层递推时必须写进新数组再整体切换，就地覆盖会让同一层的结果被当作上一层重复使用——这正是「一周只能飞一次」被破坏的方式。

这类「层 × 节点」的分层 DP 与 787、576 是同一个模子：把「步数 / 周数 / 层数」作为外层，把「位置」作为状态维度，转移沿边进行。认出模子后剩下的只是填细节。

易错点总结

转移时加 days[from][week] 而不是 days[to][week]：flights = [[0,1],[1,0]], days = [[0,0],[9,9]] → 从城市 0 飞往城市 1 时按出发地计 0 天，最终返回 9 而不是 18，整条时间线错开一周。

只靠 flights[from][to] == 1 判断、漏掉 from == to：题目规定 flights[i][i] == 0 → 任何「原地不动」的方案都不可行，flights 全零时直接返回 0，而正确答案是一直待在城市 0 的天数之和。

不可达状态用 0 而不是 -1：flights = [[0,0],[0,0]], days = [[0,0],[9,9]] 会让城市 1 凭空成为可达状态，得到不存在的收益。

就地更新 dp 而不新建 next：flights = [[0,1],[1,0]] → 本周刚更新的 dp[1] 立刻被当作上一周的状态用于转移到 dp[0]，等价于一周飞了两次，天数虚高。

初始状态写成 dp 全为 0：flights 全零、days = [[0,0],[9,9]] → 第 0 周就能「凭空出现在城市 1」，返回 18，正确答案是 0。起点必须唯一。

周数从 flights 或 days.length 读取：days 是 n × k 的矩阵 → 用 days.length 得到的是城市数，城市数与周数不等时循环次数直接错，越界或漏算。

答案只取 dp[0]：这等于强制最后回到起点，而题目没有该要求，最优路线可能停在任意城市。

把状态定义成「第 week 周开始时在 city」却仍加 days[to][week]：口径与转移不一致 → 首周或末周被重复计算 / 遗漏，结果恰好差一周的天数，且用小样例很难看出来。

相似题目

题目	难度	考察点
787. K 站中转内最便宜的航班	中等	同为「层数 × 节点」分层递推，但求最小代价且边权在边上而非落点上
576. 出界的路径数	中等	层是移动步数、节点是格子，统计方案数而非最优值，转移要取模
688. 骑士在棋盘上的概率	中等	同样按步数分层，但每步的转移带概率权重，结果是期望而非最大值
309. 买卖股票的最佳时机含冷冻期	中等	时间轴同样逐日推进，但状态维度是「持仓状态」这一小集合而非位置
188. 买卖股票的最佳时机 IV	困难	多出「已用几次交易」这一维，是本题「周 × 城市」再叠加一层限制的形态
931. 下降路径最小和	中等	逐行推进且只能走相邻三列，转移边固定，不需要邻接矩阵
1289. 下降路径最小和 II	困难	转移是「除自己外的所有列」，可用最小值与次小值把每层的 $O(n^2)$ 降到线性
322. 零钱兑换	中等	同样用一个极值哨兵表示不可达状态，考的是哨兵语义与答案兜底的处理