See 线性 DP，附相似题目（Python/Java/C++/Go）
2830. Maximize the Profit as the Salesman
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
groups = [[] for _ in range(n)]
for start, end, gold in offers:
groups[end].append((start, gold))
f = [0] * (n + 1)
for end, g in enumerate(groups):
f[end + 1] = f[end]
for start, gold in g:
f[end + 1] = max(f[end + 1], f[start] + gold)
return f[n]
|
2008. Maximum Earnings From Taxi
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
groups = [[] for _ in range(n)]
for start, end, tip in rides:
groups[end - 1].append((start - 1, end - start + tip))
f = [0] * (n + 1)
for end, g in enumerate(groups):
f[end + 1] = f[end]
for start, profit in g:
f[end + 1] = max(f[end + 1], f[start + 1] + profit)
return f[n]
|
1235. Maximum Profit in Job Scheduling
1
2
3
4
5
6
7
8
| class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
jobs = sorted(zip(endTime, startTime, profit))
f = [0] * (len(jobs) + 1)
for i, (_, st, p) in enumerate(jobs):
j = bisect_right(jobs, (st, inf), hi=i)
f[i + 1] = max(f[i], f[j] + p)
return f[-1]
|
1751. Maximum Number of Events That Can Be Attended II
1
2
3
4
5
6
7
8
9
10
| class Solution:
def maxValue(self, events: List[List[int]], k: int) -> int:
events.sort(key=lambda e: e[1])
n = len(events)
f = [[0] * (k + 1) for _ in range(n + 1)]
for i, (start, end, val) in enumerate(events):
p = bisect_left(events, start, hi=i, key=lambda e: e[1])
for j in range(1, k + 1):
f[i + 1][j] = max(f[i][j], f[p][j - 1] + val)
return f[n][k]
|
2054. Two Best Non-Overlapping Events
1
2
3
4
5
6
7
8
9
10
| class Solution:
def maxTwoEvents(self, events: List[List[int]]) -> int:
events.sort(key=lambda e: e[1])
n = len(events)
f = [[0] * 3 for _ in range(n + 1)]
for i, (start, end, val) in enumerate(events):
p = bisect_left(events, start, hi=i, key=lambda e: e[1])
for j in range(1, 3):
f[i + 1][j] = max(f[i][j], f[p][j - 1] + val)
return f[-1][2]
|