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
30
31
32
33
34
35
36
37
38
39
| from typing import List
class Solution:
def __init__(self):
self.sessions = []
self.dp = {}
def encodeState(self, pos: int, sessions: List[int]) -> str:
copy = sorted(sessions)
key = str(pos) + "$"
for session in copy:
key += str(session) + "$"
return key
def solve(self, tasks: List[int], n: int, sessionTime: int, pos: int) -> int:
if pos >= n:
return 0
key = self.encodeState(pos, self.sessions)
if key in self.dp:
return self.dp[key]
self.sessions.append(tasks[pos])
ans = 1 + self.solve(tasks, n, sessionTime, pos + 1)
self.sessions.pop()
for i in range(len(self.sessions)):
if self.sessions[i] + tasks[pos] <= sessionTime:
self.sessions[i] += tasks[pos]
ans = min(ans, self.solve(tasks, n, sessionTime, pos + 1))
self.sessions[i] -= tasks[pos]
self.dp[key] = ans
return ans
def minSessions(self, tasks: List[int], sessionTime: int) -> int:
n = len(tasks)
return self.solve(tasks, n, sessionTime, 0)
|