568. Maximum Vacation Days

Approach 1: Top-down

• Time: $O(N^2K)$
• Space: $O(NK)$

C++Java

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;
  }
}

Approach 2: Bottom-up 2D DP

• Time: $O(N^2K)$
• Space: $O(NK)$

C++Java

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];
  }
};

class Solution {
  public int maxVacationDays(int[][] flights, int[][] days) {
    final int N = days.length;
    final int K = days[0].length;
    // dp[i][j] := # of vacations can be taken from i-th city and 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)$

C++Java

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] := # of vacations can be taken from 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 = move(newDp);
    }

    return dp[0];
  }
};

class Solution {
  public int maxVacationDays(int[][] flights, int[][] days) {
    final int N = days.length;
    final int K = days[0].length;
    // dp[i] := # of vacations can be taken from 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];
  }
}