前往
大廳
主題

(Medium) Leetcode2140. Solving Questions With Brainpower

光陰LD | 2025-04-01 21:52:51 | 巴幣 2 | 人氣 16

Description:
questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
如果選擇解第0題會得3分,但接下來2題(1, 2)腦力耗盡不能解
如果選擇解第1題會得4分,但接下來3題(2,3,4)腦力耗盡不能解
可以選擇跳過當前題目
求可以得到的最大值
思考:
很明顯的DP,但要怎麼寫數學式
倒序的找,維護一個"這個位置可以得到的max"
====
一開始max的想法會TLE,因為max要O(n),沒有發揮到我現在想法的優勢
這題不解等於找"從下一題開始的最大"
====
今天打了一整天的ender lilies,快打通了。音樂好愛,boss戰在知道含意之後打得很感動,全是弦樂跟鋼琴,就算被讀指令很燥也還是打下去了
--然後,打過頭了
研究已經停3天多了,自主開始有想研究的慾望,代表我真的玩過頭了,笑死
拿到力扣3月的徽章了,開心
====
class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)
        rec = [0] * (n + 1)
        for i in range(n-1, -1, -1):
            # TLE,因為max是O(n),這樣下來就是O(n^2)
            #if i + questions[i][1] + 1 < n:
            #    rec[i] = questions[i][0] + max(rec[i + questions[i][1] + 1: ])
            #else:
            #    rec[i] = questions[i][0]
            point, position = questions[i]
            solve = point + (rec[i + position + 1] if i + position + 1 < n else 0)
            skip = rec[i+1]
            rec[i] = max(solve, skip)
        return max(rec)
送禮物贊助創作者 !
0
留言
追蹤 創作集

作者相關創作

更多創作