LeetCode 568. 最大休假天数

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 568. 最大休假天数

思路分析

解法一：动态规划（推荐）

核心思路：

定义 dp[i][j] 表示第 i 周处于城市 j 时，前 i 周能获得的最大休假天数。

状态转移：dp[i][j] = max(dp[i-1][k] + vacation[j][i])，其中城市 k 可以飞往城市 j（flights[k][j] == 1 或 k == j）。

初始状态：第 0 周只能从城市 0 出发，可停留在城市 0，或飞到有航班的城市。

结果为最后一周所有城市中 dp 值的最大值。

复杂度分析：

时间复杂度：O(K² × N)，其中 K 为城市数，N 为周数

空间复杂度：O(K)，滚动数组优化后只需一维

class Solution {
  public int maxVacationDays(int[][] flights, int[][] days) {
    int k = flights.length;
    int n = days[0].length;

    // dp[j]：当前周在城市j时的最大累计休假天数
    int[] dp = new int[k];
    Arrays.fill(dp, Integer.MIN_VALUE);

    // 初始：只能从城市0出发
    dp[0] = 0;

    for (int week = 0; week < n; week++) {
      int[] next = new int[k];
      Arrays.fill(next, Integer.MIN_VALUE);

      for (int to = 0; to < k; to++) {
        for (int from = 0; from < k; from++) {
          // from城市可达to城市（自身或有航班）
          if (from == to || flights[from][to] == 1) {
            if (dp[from] != Integer.MIN_VALUE) {
              next[to] = Math.max(next[to], dp[from] + days[to][week]);
            }
          }
        }
      }

      dp = next;
    }

    int ans = 0;
    for (int val : dp) {
      if (val != Integer.MIN_VALUE) {
        ans = Math.max(ans, val);
      }
    }

    return ans;
  }
}

func maxVacationDays(flights [][]int, days [][]int) int {
    k := len(flights)
    n := len(days[0])

    // dp[j]：当前周在城市j时的最大累计休假天数
    const minVal = math.MinInt32
    dp := make([]int, k)
    for i := range dp {
        dp[i] = minVal
    }

    // 初始：只能从城市0出发
    dp[0] = 0

    for week := 0; week < n; week++ {
        next := make([]int, k)
        for i := range next {
            next[i] = minVal
        }

        for to := 0; to < k; to++ {
            for from := 0; from < k; from++ {
                // from城市可达to城市（自身或有航班）
                if (from == to || flights[from][to] == 1) && dp[from] != minVal {
                    val := dp[from] + days[to][week]
                    if val > next[to] {
                        next[to] = val
                    }
                }
            }
        }

        dp = next
    }

    ans := 0
    for _, val := range dp {
        if val != minVal && val > ans {
            ans = val
        }
    }

    return ans
}

相似题目

题目	难度	考察点
787. K 站中转内最便宜的航班	中等	动态规划、图
1335. 工作计划的最低难度	困难	动态规划
1553. 吃掉 N 个橘子的最少天数	困难	动态规划、记忆化
1406. 石子游戏 III	困难	动态规划
1186. 删除一次得到子数组最大和	中等	动态规划
1510. 石子游戏 IV	困难	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/42471341