10 lines Python with explanation, DP


  • 0

    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])
    

Log in to reply
 

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