class Solution:
def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
""" tc O(K*N*N) sc O(NK)
1. dp(i,j): start from week j unti Kth week, fly off from city i, how many vocation days can take the most
2. exist case(base case): week >= K
3. state transition fomular:
max_days = max(days[city_i][week] + dp(city_x,week+1)) =>(week j at city i+ week j+1 at any other valid city)
"""
# dp[i][j]: max vocation days to take within K weeks from city i at week j
K = len(days[0])
n = len(flights)
@lru_cache(None)
def dp(city,week):
# base case
if week >= K:
return 0
voc = 0
cnt = 1
for dest,status in enumerate(flights[city]):
# stay : days[city][week]
# not stay: flights[city]
if status or dest == city: #flights[city][city]:
voc = max(voc, days[dest][week]+dp(dest,week+1))
# wrong expression :
#voc += max(days[city][week]+dp(city,week+1), days[dest][week]+dp(dest,week+1))
return voc
# start from week 0, fly from city 0, check how many vocation days
return dp(0,0)