public int maxVacationDays(int[][] flights, int[][] days) {
// dp[i][j] means the maximum vacations we can get in city i at week j
int[][] dp = new int[N][K];
// canReach[i][j] checks whether we can reach city i at week j, we need this table since we will check the max vacations
// we can get the last week from each city based on the value in dp[][] table. Since we always start at city 0 at the
// first week, it is meaningless to check max vacations at the last week in city i if we can not get to that city
boolean[][] canReach = new boolean[N][K];
for (int city = 0; city < N; city++) {
if (city == 0 || flights[0][city] == 1) {
dp[city][0] = days[city][0];
canReach[city][0] = true;
for (int week = 1; week < K; week++) {
for (int curCity = 0; curCity < N; curCity++) {
for (int preCity = 0; preCity < N; preCity++) {
if (canReach[preCity][week - 1] && (preCity == curCity || flights[preCity][curCity] == 1)) {
dp[curCity][week] = Math.max(dp[curCity][week], days[curCity][week] + dp[preCity][week - 1]);
canReach[curCity][week] = true;
// Check the max vacations we can get in the last week from each city
for (int city = 0; city < N; city++) {
res = Math.max(res, dp[city][K - 1]);