class Solution: def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int: # 按照终点进行分组 groups = [[] for _ in range(n+1)] for s,e,t in rides: groups[e].append((s,e-s+t)) dp = [0 for _ in range(n+2)] for end, group in enumerate(groups): dp[end+1] = dp[end] if group: for s, t in group: dp[end+1] = max(dp[end+1],dp[s+1] + t) # print(dp) return dp[n+1]
2830 Code
[]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
class Solution: def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int: dp = [0] * (n+1) # dp[3] = dp[1] + 2 # dp[1] = dp[0] # 按照最后一个节点的位置分组 groups = [[] for _ in range(n)] for s,e,g in offers: groups[e].append((s,g)) for end,x in enumerate(groups): dp[end+1] = dp[end] # 如果不买 if x: for s,g in x: dp[end+1] = max(dp[s] + g,dp[end+1]) return dp[n]
1235 Code
[]
1 2 3 4 5 6 7 8 9 10 11 12
class Solution: def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int: jobs = sorted(zip(startTime,endTime,profit),key = lambda x:x[1]) dp = (len(jobs) + 1) * [0] for i, (s,e,p) in enumerate(jobs): # 这句话的意思是说从jobs[0:i]里面找到一个end值>当前i的start的索引 # -1就是变成了找到一个小于等于当前时间s开始的最近的jobs的工作 j = bisect_right(jobs, s, hi = i, key = lambda x:x[1])-1 # print(dp[j+1]+p) dp[i+1] = max(dp[i],dp[j+1] + p) # print(dp) return dp[-1]
435 Code
[]
1 2 3 4 5 6 7 8 9
class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: n = len(intervals) intervals.sort(key = lambda x:x[1]) dp = [0] * (n+1) for i,(s,e) in enumerate(intervals): j = bisect_right(intervals,s,hi=i,key=lambda x:x[1])-1 dp[i+1] = max(dp[i],dp[j+1]+1) return n-dp[-1]
1751 Code
[]
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])-1 # hi=i 表示二分上界为 i（默认为 n） for j in range(1, k + 1): f[i + 1][j] = max(f[i][j], f[p+1][j - 1] + val) return f[n][k]
2054 Code
[]
1 2 3 4 5 6 7 8 9 10
class Solution: def maxTwoEvents(self, events: List[List[int]]) -> int: events.sort(key = lambda x:x[1]) n = len(events) dp = [[0] * (2+1) for _ in range(n+1)] for i, (s,e,v) in enumerate(events): j = bisect_left(events,s,hi = i,key = lambda x:x[1])-1 for k in range(1,2+1): dp[i+1][k] = max(dp[i][k],dp[j+1][k-1] + v) return dp[-1][-1]
