568. Maximum Vacation Days

Option 1: DP

It is easy to get DP idea but the initialization part is tricky. Situations to handle:

initializing to -float("inf") rather than 0 to mark a city as not reachable.
dp[0][0] = 0 to mark that we have to start from city 0 in the week of -1

class Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        n = len(flights)
        k = len(days[0])
        dp = [[-float("inf")] * (k+1) for _ in range(n)] # dp[i][j] max vacation days if staying in city i in the week j
        dp[0][0] = 0
        
        res = 0
        for j in range(1, k+1):
            for i in range(n):
                for p in range(n):
                    if p == i or flights[p][i]:
                        dp[i][j] = max(dp[i][j], dp[p][j-1] + days[i][j-1])
                
                if j == k: # last week
                    res = max(res, dp[i][j])
        return res

568. Maximum Vacation Days - cocoder39/coco39_LC GitHub Wiki