LeetCode 568. 最大休假天数
题目描述
题意分析
初始位于城市零，每周一早上可以乘一次直飞航班，也可以留在原地。该周休假天数取决于到达的城市和周数，要求最大化全部周的累计休假天数，最后不用回到城市零。
当前去哪个城市不仅影响本周假期，也影响以后能搭乘哪些航班，因此不能只选择本周休假最多的目的地。未来只需要知道当前周数和所在城市，可以按这两个条件保存最优累计收益。
解法：按周滚动动态规划
核心思路
[!blue]
按周记录每个城市的最优累计收益。 处理week之前，dp[city]表示前面各周已经结束、目前在该城市时的最大累计天数。到达同一城市且周数相同的两段行程，未来可选航班和休假安排完全一样，所以只需保留累计天数较多的一段。初始尚未休假，只有城市零可达，令
dp[0] = 0，其他状态为-1。合法累计天数都非负，所以-1能区分“到不了”与“到得了但休假零天”。第一周也按正常转移处理，因而可以在第一次休假前先搭乘航班。枚举可达出发城市
from和目的城市to：只有from == to或flights[from][to] == 1时可以转移，候选收益为dp[from] + days[to][week]。飞行在周初完成，本周收益必须算目的城市；航班是有向的，不能默认反方向也能飞，停留则不依赖对角线航班值。
next[to]取全部合法来源的最大候选。任何合法行程都能拆成前几周的行程与本周一次停留或直飞，所以枚举来源不会遗漏最优选择；每条转移也都符合本周限制。新旧数组分开，使所有转移只读取上周状态，避免把刚到达的城市再作为本周出发点继续飞行。每周结束后用
next替换dp，处理完全部周数再取任意城市的最大值。始终可以停留在城市零，所以至少存在一条合法行程；没有任何航班时，结果就是城市零各周的休假天数总和。
解题步骤
- 初始化城市零可达，其他城市不可达。
- 每周准备新的不可达状态数组。
- 枚举停留或直飞，按目的地天数更新最大值。
- 切换到新一层，结束后取最大终态。
代码实现
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(KN²)$，K 为周数，N 为城市数。
- 空间复杂度：$O(N)$，只保留两层城市状态。
关键点总结
[!green]
- 本周收益属于目的地，飞行在周初完成。
- 停留由 from==to 单独允许，不依赖自环航班。
- 不可达与合法零收益需要区分。
易错点总结
[!yellow]
- 初始所有城市都设为零：相当于免费选择出发城市。
- 加出发地天数：收益错开本周实际所在位置。
- 直接覆盖旧层：可能在一周内重复飞行并累加收益。
- 只返回城市零状态：错误要求最后回到起点。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 787. K 站中转内最便宜的航班 | 中等 | 同样按有限步数或阶段在城市间做DP，本题每周累计最大假期，原题在最多中转次数内取最低票价。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！