Skip to content

568. Maximum Vacation Days 👍

Approach 1: Top-down

  • Time: $O(n^2k)$
  • Space: $O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
    vector<vector<int>> mem(days.size(), vector<int>(days[0].size(), INT_MIN));
    return maxVacationDays(flights, days, 0, 0, mem);
  }

 private:
  // Returns the number of vacations that can be taken from the i-th city and
  // the k-th week.
  int maxVacationDays(const vector<vector<int>>& flights,
                      const vector<vector<int>>& days, int i, int k,
                      vector<vector<int>>& mem) {
    if (k == days[0].size())
      return 0;
    if (mem[i][k] != INT_MIN)
      return mem[i][k];

    // Stay at the j-th city or fly from the i-th city to the j-th city.
    for (int j = 0; j < flights.size(); ++j)
      if (j == i || flights[i][j] == 1)
        mem[i][k] = max(mem[i][k], days[j][k] + maxVacationDays(flights, days,
                                                                j, k + 1, mem));

    return mem[i][k];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int maxVacationDays(int[][] flights, int[][] days) {
    int[][] mem = new int[days.length][days[0].length];
    Arrays.stream(mem).forEach(A -> Arrays.fill(A, Integer.MIN_VALUE));
    return maxVacationDays(flights, days, 0, 0, mem);
  }

  // Returns the number of vacations that can be taken from the i-th city and
  // the k-th week.
  private int maxVacationDays(int[][] flights, int[][] days, int i, int k, int[][] mem) {
    if (k == days[0].length)
      return 0;
    if (mem[i][k] != Integer.MIN_VALUE)
      return mem[i][k];

    // Stay at the j-th city or fly from the i-th city to the j-th city.
    for (int j = 0; j < flights.length; j++)
      if (j == i || flights[i][j] == 1)
        mem[i][k] = Math.max(mem[i][k], days[j][k] + maxVacationDays(flights, days, j, k + 1, mem));

    return mem[i][k];
  }
}

Approach 2: Bottom-up 2D DP

  • Time: $O(n^2k)$
  • Space: $O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
    const int N = days.size();
    const int K = days[0].size();
    // dp[i][k] := the number of vacations that can be taken from the i-th city
    // and the k-th week
    vector<vector<int>> dp(N, vector<int>(K + 1));

    for (int k = K - 1; k >= 0; --k)
      for (int i = 0; i < N; ++i) {
        dp[i][k] = days[i][k] + dp[i][k + 1];
        for (int j = 0; j < N; ++j)
          if (flights[i][j] == 1)
            dp[i][k] = max(dp[i][k], days[j][k] + dp[j][k + 1]);
      }

    return dp[0][0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int maxVacationDays(int[][] flights, int[][] days) {
    final int N = days.length;
    final int K = days[0].length;
    // dp[i][k] := the number of vacations that can be taken from the i-th city
    // and the k-th week
    int[][] dp = new int[N][K + 1];

    for (int k = K - 1; k >= 0; --k)
      for (int i = 0; i < N; ++i) {
        dp[i][k] = days[i][k] + dp[i][k + 1];
        for (int j = 0; j < N; ++j)
          if (flights[i][j] == 1)
            dp[i][k] = Math.max(dp[i][k], days[j][k] + dp[j][k + 1]);
      }

    return dp[0][0];
  }
}

Approach 3: Bottom-up 1D DP

  • Time: $O(n^2k)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
    const int N = days.size();
    const int K = days[0].size();
    // dp[i] := the number of vacations that can be taken from the i-th city
    vector<int> dp(N);

    for (int k = K - 1; k >= 0; --k) {
      vector<int> newDp(N);
      for (int i = 0; i < N; ++i) {
        newDp[i] = days[i][k] + dp[i];
        for (int j = 0; j < N; ++j)
          if (flights[i][j] == 1)
            newDp[i] = max(newDp[i], days[j][k] + dp[j]);
      }
      dp = std::move(newDp);
    }

    return dp[0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int maxVacationDays(int[][] flights, int[][] days) {
    final int N = days.length;
    final int K = days[0].length;
    // dp[i] := the number of vacations that can be taken from the i-th city
    int[] dp = new int[N];

    for (int k = K - 1; k >= 0; --k) {
      int[] newDp = new int[N];
      for (int i = 0; i < N; ++i) {
        newDp[i] = days[i][k] + dp[i];
        for (int j = 0; j < N; ++j)
          if (flights[i][j] == 1)
            newDp[i] = Math.max(newDp[i], days[j][k] + dp[j]);
      }
      dp = newDp;
    }

    return dp[0];
  }
}