# 10 lines Python with explanation, DP

• 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 `None`
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 `None` again.

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[0])
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][0] = 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])
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.