作者DJYOMIYAHINA (通通打死)
看板Marginalman
標題Re: [閒聊] 每日leetcode
時間Tue Jul 8 23:34:09 2025
一開始用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