Maximum Vacation Days

hard array dp matrix

Problem

N cities, K weeks. flights[i][j]=1 means a Monday flight from i to j. days[i][w] is the vacation days in city i on week w. Start in city 0. Max total days?

Inputflights=[[0,1,1],[1,0,1],[1,1,0]], days=[[1,3,1],[6,0,3],[3,3,3]]

Output12

DP iterating weeks backwards from K-1; O(K · N²).

flights (rows ; ,)

days (rows ; ,)

def max_vacation_days(flights, days):
    N, K = len(flights), len(days[0])
    INF = float("-inf")
    dp = [INF] * N; dp[0] = 0
    for w in range(K):
        nxt = [INF] * N
        for cur in range(N):
            if dp[cur] == INF: continue
            for nxt_city in range(N):
                if nxt_city == cur or flights[cur][nxt_city] == 1:
                    nxt[nxt_city] = max(nxt[nxt_city], dp[cur] + days[nxt_city][w])
        dp = nxt
    return max(dp)

function maxVacationDays(flights, days) {
  const N = flights.length, K = days[0].length;
  const NEG = -Infinity;
  let dp = new Array(N).fill(NEG);
  dp[0] = 0;
  for (let w = 0; w < K; w++) {
    const next = new Array(N).fill(NEG);
    for (let cur = 0; cur < N; cur++) {
      if (dp[cur] === NEG) continue;
      for (let c = 0; c < N; c++) {
        if (c === cur || flights[cur][c] === 1) next[c] = Math.max(next[c], dp[cur] + days[c][w]);
      }
    }
    dp = next;
  }
  return Math.max(...dp);
}

class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        int N = flights.length, K = days[0].length;
        int[] dp = new int[N];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = 0;
        for (int w = 0; w < K; w++) {
            int[] next = new int[N]; Arrays.fill(next, Integer.MIN_VALUE);
            for (int cur = 0; cur < N; cur++) {
                if (dp[cur] == Integer.MIN_VALUE) continue;
                for (int c = 0; c < N; c++) {
                    if (c == cur || flights[cur][c] == 1)
                        next[c] = Math.max(next[c], dp[cur] + days[c][w]);
                }
            }
            dp = next;
        }
        int best = 0;
        for (int v : dp) best = Math.max(best, v);
        return best;
    }
}

int maxVacationDays(vector>& flights, vector>& days) {
    int N = flights.size(), K = days[0].size();
    vector dp(N, INT_MIN);
    dp[0] = 0;
    for (int w = 0; w < K; w++) {
        vector next(N, INT_MIN);
        for (int cur = 0; cur < N; cur++) {
            if (dp[cur] == INT_MIN) continue;
            for (int c = 0; c < N; c++)
                if (c == cur || flights[cur][c] == 1) next[c] = max(next[c], dp[cur] + days[c][w]);
        }
        dp = next;
    }
    return *max_element(dp.begin(), dp.end());
}

Explanation

Each week you are sitting in some city, and on Monday you may either stay or fly to another city that has a direct flight. We track the most vacation days reachable per city, week by week.

The state is dp[city] = the maximum vacation days collected if you are in that city at the start of the current week. We start with dp[0] = 0 (you begin in city 0) and everything else as -infinity (unreachable).

For each week we build a fresh next array. From every reachable cur city, we look at each destination c that is either the same city or has flights[cur][c] == 1, and update next[c] = max(next[c], dp[cur] + days[c][w]). After processing the week, next becomes the new dp.

Example: with the sample flights and days, following the best stay/fly choices week by week accumulates 12 vacation days, which is max(dp) at the end.

For each of K weeks we examine every pair of cities, so the running time is O(K · N²) with only O(N) space.

Time: O(K·N²) Space: O(N)