多維DP
含有「多維DP」共 19 篇內容
全部內容
發佈日期由新至舊
付費限定
題目敘述 664. Strange Printer
有一台奇怪的印表機，
每次操作只能連續印同樣的字母，但是列印的長度可以自由控制。
而且，印刷的時候，可以蓋過去舊的字元。
(這邊當然不合常理，讀者可以理解成塗了立可帶再蓋過去的情境)
給定一個輸入字串s，請問最少需要幾次操作，才能印出字串s?
付費限定
給定木板的長度和切割點位置，找到最小總切割成本。透過DP動態規劃和區間DP框架，定義DP狀態並推導出最小切割成本的遞迴關係式。複雜度分析為時間複雜度O(n^3)和空間複雜度O(n^2)。關鍵知識點在於挖掘切割問條的共通模式，透過範例和圖解輔助思考。
付費限定
Paint House
題目會給定一個成本陣列costs，分別代表每棟房屋粉刷成紅色、藍色、綠色的成本。
請問粉刷所有房屋的最小成本是多少，而且相鄰的房屋不可同一種顏色。
😊😊😊我來啦！
付費限定
題目敘述 Combination Sum IV
給定一個輸入陣列nums，和目標值target，從nums裡面挑數字去湊出總和 = target，數字可以重複挑選。
請問有多少排列數可以湊出target？
註: 排列數的意思就是位置不同代表兩種不同的方法數。
吃飽飽😁
付費限定
題目敘述 Distinct Subsequences
給定一個字串s和目標t，請問有多少個s的子序列可以完美匹配目標t ?
也就是說，有多少個s的子序列和目標t相等?
測試範例
Input: s = "rabbbit", t = "rabbit"
Output: 3
😘😘😘早
付費限定
題目敘述 Longest Palindromic Subsequence
給定一個字串s，請找出字串s的最長回文子序列的長度。
註: 子序列 不要求一定要連續。
測試範例
Input: s = "bbbab"
Output: 4
我希望自己下輩子能搞懂這些…欸…會不會下輩子這些東西又退流行了🤔嗯…那我要當考古學者。
付費限定
題目敘述 Longest Palindromic Substring
給定一個輸入字串s，請找出最長的回文子字串。
答案可能不只一個，回傳任何一個合法的答案皆可。
小松鼠～我來囉～😁
付費限定
Minimum Path Sum
給定一個矩陣，每個格子點代表經過的對應成本。
每回合可以往右移動一格或往下移動一格。
請問從起點左上角 走到 終點右下角的最小路徑成本總和是多少?
😵😵😵還是來吃東西好了🥗🍣🍸
付費限定
給定一個整數陣列nums，請找出等最長差數列的長度是多少?
🤯🤯🤯欸…天書！
付費限定
給定一個輸入陣列，計算最長遞增子序列的總數。本題和Longest Common Subsequence相似，需要設定一個計數器，記錄最長遞增子序列的數量。透過DP模型的化簡方式來解決問題。時間複雜度為O(n^2)，空間複雜度為O(n)。主要使用回頭看的技巧，找出比較小的元素去延伸遞增子序列的長度。
理化在手、天下我有！🤨🤨🤨