-
Notifications
You must be signed in to change notification settings - Fork 0
/
1066. Campus Bikes II
29 lines (24 loc) · 986 Bytes
/
1066. Campus Bikes II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
def dist(p1, p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
memory = [0 for i in range(1 << len(bikes))]
dp = [[0 for i in range(len(bikes))] for j in range(len(workers))]
for i in range(len(workers)):
p1 = workers[i]
for j in range(len(bikes)):
p2 = bikes[j]
dp[i][j] = dist(p1, p2)
def dfs(i, state):
if i == len(workers):
return 0
if memory[state] != 0:
return memory[state]
ans = 999999
for j in range(len(bikes)):
if 1<<j & state == 0:
memory[state]
ans = min(ans, dp[i][j] + dfs(i+1, state|1<<j))
memory[state] = ans
return ans
return dfs(0, 0)