We keep a matrix, where each row corresponds a week, each column corresponds a city.
Each cell notes the days of the longest vacations possible at a certain city in a certain week. If the city is impossible to reach, notes
The first row is
0, None, None, ... , None, means before the first week, the employee is at the first city.
In the interation, for every cell, we calculate whether there is a flight from last city to current city, note that as
last_city, if it's reachable, its value should be this week's vacations
+ the max of all possible last vacations, if it's not reachable, note as
The max of the last row will tell us the max vacations of all routes.
class Solution(object): def maxVacationDays(self, flights, days): """ :type flights: List[List[int]] :type days: List[List[int]] :rtype: int """ no_of_citys, no_of_weeks = len(days), len(days) for i in range(no_of_citys): flights[i][i] = 1 dp = [[None] * no_of_citys for i in range(no_of_weeks + 1)] dp = 0 for i in range(1, no_of_weeks + 1): for j in range(no_of_citys): last_city = [True if lc2 is not None and flights[lc1][j] else False for lc1, lc2 in enumerate(dp[i-1])] dp[i][j] = days[j][i-1] + max([dp[i-1][lc1] for lc1, lc2 in enumerate(last_city) if lc2]) if any(last_city) else None return max(dp[-1])