區間DP
含有「區間DP」共 13 篇內容
全部內容
發佈日期由新至舊
付費限定
給定木板的長度和切割點位置，找到最小總切割成本。透過DP動態規劃和區間DP框架，定義DP狀態並推導出最小切割成本的遞迴關係式。複雜度分析為時間複雜度O(n^3)和空間複雜度O(n^2)。關鍵知識點在於挖掘切割問條的共通模式，透過範例和圖解輔助思考。
付費限定
Paint House
題目會給定一個成本陣列costs，分別代表每棟房屋粉刷成紅色、藍色、綠色的成本。
請問粉刷所有房屋的最小成本是多少，而且相鄰的房屋不可同一種顏色。
😊😊😊我來啦！
付費限定
題目敘述 Solving Questions With Brainpower
給定一個測驗題陣列，每個欄位都是一個pair，
分別記錄測驗題做完可以得到的分數，和需要的冷卻時間
(也就是會有一段時間不能作答接下來的題目)。
請問在最佳的答題策略下，最多可以獲得多少分數?
來打卡😁
付費限定
題目敘述 Binary Tree Maximum Path Sum
給定一個二元樹，請找出最大的區間路徑和是多少?
註:
區間路徑和 = 某個節點a -> 某個節點b的路徑節點值總和。
🏝🏝🏝
付費限定
題目敘述 Distinct Subsequences
給定一個字串s和目標t，請問有多少個s的子序列可以完美匹配目標t ?
也就是說，有多少個s的子序列和目標t相等?
測試範例
Input: s = "rabbbit", t = "rabbit"
Output: 3
😘😘😘早
付費限定
題目敘述 Minimum Cost For Tickets
題目會給定兩個陣列。
第一個是日期陣列days，代表外出旅遊的是哪幾天。
第二個是成本陣列costs，代表火車一日票、七日票、30日的月票的票價。
請問火車旅行支出的最小費用是多少？
專業分析，超厲害
付費限定
題目敘述 Longest Palindromic Substring
給定一個輸入字串s，請找出最長的回文子字串。
答案可能不只一個，回傳任何一個合法的答案皆可。
小松鼠～我來囉～😁
付費限定
題目會給我們一個nums陣列，分別代表每棟房屋的價值，也就是房屋內有的現金數量。
題目敘述給的情境是假想盜賊要偷東西，限制是相鄰的兩棟房屋不能一起偷，只能選擇其中一棟，否則就會觸發警報器。第一棟和最後一棟也被視為相鄰。
請問怎麼選擇哪幾棟房屋下手，可以
🏢🏢🏢
付費限定
本篇文章介紹了區間DP及博弈論Min/Max最佳化的相關概念，以及如何應用這些概念來計算最佳策略進行取石頭遊戲的模擬。文章實際分析了演算法、實用的加速技巧和關鍵知識點。這篇文章對於想要學習區間DP的讀者來說非常有價值。
付費限定
題目敘述
給定一個piles陣列，裡面對應到每堆石頭的數量。
Alice 和 Bob玩輪流取石頭的遊戲，總共有n堆石頭，每堆的石頭數量有多有少。
Alice先取，接著Bob，反覆交替，每回合輪到的人可以從當下的第一堆或者最後一堆，拿走那堆對應的石頭。
最後比誰拿到的石頭總數量比較多就獲勝。
我剛剛想說DP是什麼🤔，原來是動態規劃🤣🤣🤣DP在程式考試很常考，不過用Python很怕時間不足（我講的是Apcs）不過也有可能是優化問題🤔🤔🤔