难度: Hard
Submission
运行时间: 227 ms
内存: 16.8 MB
class Solution:
# # dfs
def maxVacationDays1(self, flights: List[List[int]], days: List[List[int]]) -> int:
@cache
def dfs(day, city):
if day == len(days[0]):
return 0
res = dfs(day + 1, city) + days[city][day]
for i in range(len(flights)):
if not flights[city][i]:
continue
res = max(res, dfs(day + 1, i) + days[i][day])
return res
return dfs(0, 0)
# 动态规划
def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
n, k = len(flights), len(days[0])
# 记录可达城市信息
dct = defaultdict(list)
for i in range(n):
for j in range(n):
if flights[i][j]:
dct[i].append(j)
# 初始化
pre = [float('-inf')]*n
pre[0] = 0
for j in range(k):
cur = pre[:]
for i in range(n):
# 状态转移，从城市i出发到达x
for x in dct[i]:
if pre[i] + days[x][j] > cur[x]:
cur[x] = pre[i] + days[x][j]
# 停留在城市i
if pre[i] + days[i][j] > cur[i]:
cur[i] = pre[i] + days[i][j]
pre = cur[:]
return max(pre)
Explain
该题解提供了两种解法。第一种是深度优先搜索（DFS）的递归解法，通过记忆化搜索避免重复计算。从第0天开始，对每个城市进行DFS，计算从该城市出发能获得的最大休假天数。第二种是动态规划解法，用两个数组pre和cur分别记录上一天和当前天每个城市能获得的最大休假天数。对于每一天，遍历所有城市，更新cur数组，考虑从上一天能到达的城市出发或停留在当前城市的休假天数，取最大值。最后返回最后一天各城市的最大休假数。
时间复杂度: O(n^2*k)
空间复杂度: O(n^2)
class Solution:
# DFS解法
def maxVacationDays1(self, flights: List[List[int]], days: List[List[int]]) -> int:
@cache
def dfs(day, city):
# 递归出口：假期结束
if day == len(days[0]):
return 0
# 停留在当前城市
res = dfs(day + 1, city) + days[city][day]
# 遍历所有可以到达的城市
for i in range(len(flights)):
if not flights[city][i]:
continue
# 从可以到达的城市出发能获得的最大休假天数
res = max(res, dfs(day + 1, i) + days[i][day])
return res
return dfs(0, 0)
# 动态规划解法
def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
n, k = len(flights), len(days[0])
# 记录可达城市信息
dct = defaultdict(list)
for i in range(n):
for j in range(n):
if flights[i][j]:
dct[i].append(j)
# 初始状态：第0天只能从城市0出发
pre = [float('-inf')]*n
pre[0] = 0
# 遍历每一天
for j in range(k):
cur = pre[:]
# 遍历每个城市
for i in range(n):
# 从城市i出发到达城市x
for x in dct[i]:
if pre[i] + days[x][j] > cur[x]:
cur[x] = pre[i] + days[x][j]
# 停留在城市i
if pre[i] + days[i][j] > cur[i]:
cur[i] = pre[i] + days[i][j]
pre = cur[:]
return max(pre)
Explore
在DFS解法中，使用了Python的`@cache`装饰器来确保递归过程中不会重复计算相同的状态。这个装饰器自动保存每次函数调用的结果，并在后续遇到相同参数的调用时，直接返回已保存的结果。这样，每个状态 `(day, city)` 的结果只计算一次，避免了重复的计算，从而显著提高了算法的效率。
`@cache`装饰器是Python标准库中`functools`模块提供的一个功能，它能够自动地保存函数的调用结果及其对应的参数。在这种情况下，它保存了`dfs`函数的参数`day`和`city`以及函数返回的结果。当`dfs`函数再次被相同的参数`(day, city)`调用时，装饰器会直接返回之前保存的结果，而不是重新执行函数体。这样减少了重复计算，提高了程序的执行效率。
在动态规划解法中，`pre`数组用于保存上一天每个城市的最大休假天数，而`cur`数组则用于计算并存储当前天每个城市的最大休假天数。使用两个数组来交替更新的原因是，我们需要保留上一天的数据来计算当前天的值。如果只用一个数组，那么在更新当前天的值时就会覆盖掉上一天的数据，导致无法正确计算。通过交替使用`pre`和`cur`，我们可以在不丢失必要数据的情况下更新状态，同时也避免了额外的内存开销。
在动态规划的初始状态设置中，`pre[0]`被设为0因为假设只有城市0是在第0天可达的起点。其他城市的初始值设为负无穷大是为了表示在第0天，这些城市是不可达的。这种设置避免了在后续迭代中错误地考虑从不可达城市出发的情况。随着算法的进行，只有当某个城市通过某种路径变得可达时，其对应的值才会被更新为非负无穷大的值。这样确保了动态规划的正确性和有效性。