一共有n个楼,给出一些requests,requests
i=[from
i, to
i],代表一个人要求从from到to楼,问最多可以满足多少个requests,使得最后每栋楼进出的人数一样
直接DFS爆搜
1 #1601
2 #Runtime: 1254 ms (Beats 62.13%)
3 #Memory: 16.6 MB (Beats 33.98%)
4
5 class Solution:
6 def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
7 ans = 0
8 remain = [0] * n
9
10 def DFS(x, cnt):
11 nonlocal ans
12 if x == len(requests):
13 for i in range(n):
14 if remain[i]:
15 return
16 ans = max(ans, cnt)
17 return
18 remain[requests[x][0]] -= 1
19 remain[requests[x][1]] += 1
20 DFS(x + 1, cnt + 1)
21 remain[requests[x][0]] += 1
22 remain[requests[x][1]] -= 1
23 DFS(x + 1, cnt)
24
25 DFS(0, 0)
26 return ans