Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

568. Maximum Vacation Days

Time: $O(N^2K)$

Space: $O(NK)$

			


class Solution {
 public:
  int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
    // dp[i][j] := # of vacations can be taken from i-th city and k-th week
    dp.resize(days.size(), vector<int>(days[0].size(), INT_MIN));
    return maxVacationDays(flights, days, 0, 0);
  }

 private:
  vector<vector<int>> dp;

  int maxVacationDays(const vector<vector<int>>& flights,
                      const vector<vector<int>>& days, int i, int k) {
    if (k == days[0].size())
      return 0;
    if (dp[i][k] != INT_MIN)
      return dp[i][k];

    int ans = 0;

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

    return dp[i][k] = ans;
  }
};




			


class Solution {
  public int maxVacationDays(int[][] flights, int[][] days) {
    // dp[i][j] := # of vacations can be taken from i-th city and k-th week
    dp = new int[days.length][days[0].length];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MIN_VALUE));
    return maxVacationDays(flights, days, 0, 0);
  }

  private int[][] dp;

  private int maxVacationDays(int[][] flights, int[][] days, int i, int k) {
    if (k == days[0].length)
      return 0;
    if (dp[i][k] != Integer.MIN_VALUE)
      return dp[i][k];

    int ans = 0;

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

    return dp[i][k] = ans;
  }
}




			


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][j] := # of vacations can be taken from i-th city and 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];
  }
};