一開始用dfs 哈哈 怎麼可能過 後來偷看一下往dp走 dp[i][j]代表只看events[:j+1]的情況下，取i個的最大value dp[i][j]就可以分成有取第j個的情況&沒取第j個的情況 然後繼續下去 比較特別的點是 1. 取了第j個之後 找dp array你得先找到end_time比第j個event的start_time早的活動們 就得先對events sort by endtime 這樣可以用binary search找到 2. 很有可能你根本取不滿i個，這邊我直接用-10**10擋掉 很醜 對ㄚ 之後再來看看能不能改漂亮一點 def maxValue(self, events: List[List[int]], k: int) -> int: ans = -1 n = len(events) events.sort(key=lambda item:item[1]) dp = [[-10**10 for _ in range(n)] for _ in range(k+1)] # init for j in range(n): dp[0][j] = 0 # dp for i in range(1, k+1): for j in range(i-1, n): val_unpick = dp[i][j-1] idx_tmp = bisect_left(events, events[j][0], key=lambda item:item[1 ])-1 if idx_tmp==-1 and i==1: val_pick = 0 elif idx_tmp==-1 and i>1: val_pick = -10**10 else: val_pick = dp[i-1][idx_tmp] dp[i][j] = max(val_unpick, val_pick+events[j][2]) ans = -1 for i in range(k+1): ans = max(ans, dp[i][-1]) return ans # def dfs(idx, cnt, cur_val): # nonlocal ans # if idx>=n or cnt>=k: # return cur_val # if mem[cnt-1][idx] != -1: # return mem[cnt-1][idx]+cur_val # next_idx_picked = bisect_right(events, events[idx][1], key=lambda item: item[0]) # next_idx_unpicked = idx+1 # ans = max(ans, # dfs(next_idx_picked, cnt+1, cur_val+events[idx][2]), # dfs(next_idx_unpicked, cnt, cur_val)) # return ans # return dfs(0, 0, 0) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.58.28 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1751988851.A.48C.html