小松鼠的演算法樂園
DP動態規劃 特訓班
17
免費公開
55
付費限定
房間資訊
付費訂閱
以Leetcode國際版官方精選DP動態規劃測驗題為大綱 以獨門的 DP三段式框架 和 化簡技巧 為輔 幫助讀者徹底理解DP的思想與意義 熟練DP框架與常見的DP演算法模板 以明確的DP演算法推演框架 協助讀者從理解題意開始,建立演算法,寫出Python程式碼。 幫助讀者擺脫遇到一題硬背一題解答的困境!
全部
格子點DP
數列/子序列 DP
字串/區間 DP
最佳化/交易模擬DP
樹型DP
取捨DP
全部
格子點DP
數列/子序列 DP
字串/區間 DP
最佳化/交易模擬DP
樹型DP
取捨DP
全部類型
免費與付費
最新發佈
最新發佈
小松鼠
2024/09/13
♒成雙成對 子陣列的XOR query_XOR Queries of a Subarray_Leetcode #1310
給定一個整數陣列arr,和一串區間XOR請求queries。 請計算queries所請求的區間XOR值,並且以陣列的形式返回答案。
#
python
#
leetcode
#
algorithm
12
5
小松鼠
2024/09/13
♒成雙成對 子陣列的XOR query_XOR Queries of a Subarray_Leetcode #1310
給定一個整數陣列arr,和一串區間XOR請求queries。 請計算queries所請求的區間XOR值,並且以陣列的形式返回答案。
#
python
#
leetcode
#
algorithm
12
5
小松鼠
2024/08/27
🚗用圖論+DP來找 成功機率最高的路徑 Path w/ Max Probability_Leetcode #1514
Path with Maximum Probability 題目給定一個無向圖(雙向移動皆可), 提供每條邊的起終點,和每條邊對應的通過時的成功機率。 請問從起點start走到終點end的最高成功機率是多少? 如果完全沒有路徑可以抵達,則返回0。
#
python
#
leetcode
#
algorithm
6
8
小松鼠
2024/08/27
🚗用圖論+DP來找 成功機率最高的路徑 Path w/ Max Probability_Leetcode #1514
Path with Maximum Probability 題目給定一個無向圖(雙向移動皆可), 提供每條邊的起終點,和每條邊對應的通過時的成功機率。 請問從起點start走到終點end的最高成功機率是多少? 如果完全沒有路徑可以抵達,則返回0。
#
python
#
leetcode
#
algorithm
6
8
小松鼠
2024/08/21
用字串DP來操作印表機 奇怪的印表機_Leetcode #664
題目敘述 664. Strange Printer 有一台奇怪的印表機, 每次操作只能連續印同樣的字母,但是列印的長度可以自由控制。 而且,印刷的時候,可以蓋過去舊的字元。 (這邊當然不合常理,讀者可以理解成塗了立可帶再蓋過去的情境) 給定一個輸入字串s,請問最少需要幾次操作,才能印出字串s?
#
python
#
leetcode
#
algorithm
8
2
小松鼠
2024/08/21
用字串DP來操作印表機 奇怪的印表機_Leetcode #664
題目敘述 664. Strange Printer 有一台奇怪的印表機, 每次操作只能連續印同樣的字母,但是列印的長度可以自由控制。 而且,印刷的時候,可以蓋過去舊的字元。 (這邊當然不合常理,讀者可以理解成塗了立可帶再蓋過去的情境) 給定一個輸入字串s,請問最少需要幾次操作,才能印出字串s?
#
python
#
leetcode
#
algorithm
8
2
小松鼠
2024/08/20
用DP來玩遊戲 石頭遊戲 III_Stone Game III_Leetcode #1406
題目敘述 1406. Stone Game III Alice 和 Bob 輪流玩取石頭的遊戲。 輸入陣列stoneValue 代表每顆石頭對應的價值。 規則如下: 每個人每回合可以從剩餘的石頭,從前面拿一顆、兩顆、或三顆石頭。 兩個人輪流交替拿。Alice先手,第一回合Alice
#
python
#
game
#
stonegame
9
2
小松鼠
2024/08/20
用DP來玩遊戲 石頭遊戲 III_Stone Game III_Leetcode #1406
題目敘述 1406. Stone Game III Alice 和 Bob 輪流玩取石頭的遊戲。 輸入陣列stoneValue 代表每顆石頭對應的價值。 規則如下: 每個人每回合可以從剩餘的石頭,從前面拿一顆、兩顆、或三顆石頭。 兩個人輪流交替拿。Alice先手,第一回合Alice
#
python
#
game
#
stonegame
9
2
小松鼠
2024/08/19
字串DP: 用最少的操作次數生成字串_2 Keys Keyboard_Leetcode #650
題目敘述 Leetcode: 650. 2 Keys Keyboard 一開始初始化的時候,記事本上只有一個字元'A'。 只允許下列兩種操作 複製目前記事本上的整個字串。 貼上之前複製的內容,串接在尾端。 請問,最少需要幾個操作, 才能製造出內容都是 "AAA...A",長度為n的字串?
#
python
#
leetcode
#
algorithm
6
2
小松鼠
2024/08/19
字串DP: 用最少的操作次數生成字串_2 Keys Keyboard_Leetcode #650
題目敘述 Leetcode: 650. 2 Keys Keyboard 一開始初始化的時候,記事本上只有一個字元'A'。 只允許下列兩種操作 複製目前記事本上的整個字串。 貼上之前複製的內容,串接在尾端。 請問,最少需要幾個操作, 才能製造出內容都是 "AAA...A",長度為n的字串?
#
python
#
leetcode
#
algorithm
6
2
小松鼠
2024/08/18
數列DP應用: Ugly Number II _Leetcode #264
題目敘述: 264. Ugly Number II 定義Ugly number序列是質因數只有2, 3, 5的正整數數列。 也就是說 x = 2^i * 3^j * 5^k, where i >= 0, j >= 0, k >= 0 請計算第n項的Ugly number 等於多少?
#
python
#
leetcode
#
algorithm
7
5
小松鼠
2024/08/18
數列DP應用: Ugly Number II _Leetcode #264
題目敘述: 264. Ugly Number II 定義Ugly number序列是質因數只有2, 3, 5的正整數數列。 也就是說 x = 2^i * 3^j * 5^k, where i >= 0, j >= 0, k >= 0 請計算第n項的Ugly number 等於多少?
#
python
#
leetcode
#
algorithm
7
5
小松鼠
2024/07/30
用DP來精打細算 切割木條的最小成本 Min Cost to Cut a Stick_Leetcode #1547
給定木板的長度和切割點位置,找到最小總切割成本。透過DP動態規劃和區間DP框架,定義DP狀態並推導出最小切割成本的遞迴關係式。複雜度分析為時間複雜度O(n^3)和空間複雜度O(n^2)。關鍵知識點在於挖掘切割問條的共通模式,透過範例和圖解輔助思考。
#
python
#
leetcode
#
algorithm
10
1
小松鼠
2024/07/30
用DP來精打細算 切割木條的最小成本 Min Cost to Cut a Stick_Leetcode #1547
給定木板的長度和切割點位置,找到最小總切割成本。透過DP動態規劃和區間DP框架,定義DP狀態並推導出最小切割成本的遞迴關係式。複雜度分析為時間複雜度O(n^3)和空間複雜度O(n^2)。關鍵知識點在於挖掘切割問條的共通模式,透過範例和圖解輔助思考。
#
python
#
leetcode
#
algorithm
10
1
小松鼠
2024/07/28
圖論+DP: 字串轉換的最小成本 Min Cost to Convert String I_Leetcode #2976
題目敘述: Minimum Cost to Convert String I 給定字元轉換映射表original, changes和對硬的成本陣列cost。 請問字串source轉換到字串destination的最小成本是多少? 如果無解,請返回-1 如果有解,請返回整體的轉換最小成本。
#
python
#
leetcode
#
algorithm
13
5
小松鼠
2024/07/28
圖論+DP: 字串轉換的最小成本 Min Cost to Convert String I_Leetcode #2976
題目敘述: Minimum Cost to Convert String I 給定字元轉換映射表original, changes和對硬的成本陣列cost。 請問字串source轉換到字串destination的最小成本是多少? 如果無解,請返回-1 如果有解,請返回整體的轉換最小成本。
#
python
#
leetcode
#
algorithm
13
5
小松鼠
2024/06/14
用格子點DP來解 三角形最小成本下降路徑 Triangle_Leetcode #120
題目敘述 Triangle 題目會給我們一個三角形的二維陣列triangle ,每個元素分別代表每個格子的成本,請問我們從最頂端到底部的下墜路徑的最小成本總和是多少? 每次下墜到下一排的時候,可以有兩種選擇: 1.往左下方的格子點移動。 2.往右下方的格子點移動。 測試範例 Examp
#
python
#
leetcode
#
algorithm
14
3
小松鼠
2024/06/14
用格子點DP來解 三角形最小成本下降路徑 Triangle_Leetcode #120
題目敘述 Triangle 題目會給我們一個三角形的二維陣列triangle ,每個元素分別代表每個格子的成本,請問我們從最頂端到底部的下墜路徑的最小成本總和是多少? 每次下墜到下一排的時候,可以有兩種選擇: 1.往左下方的格子點移動。 2.往右下方的格子點移動。 測試範例 Examp
#
python
#
leetcode
#
algorithm
14
3
小松鼠
2024/06/12
用取捨DP框架來上色 粉刷房屋I_Paint House_Leetcode #256
Paint House 題目會給定一個成本陣列costs,分別代表每棟房屋粉刷成紅色、藍色、綠色的成本。 請問粉刷所有房屋的最小成本是多少,而且相鄰的房屋不可同一種顏色。
#
python
#
algorithm
#
leetcode
16
5
小松鼠
2024/06/12
用取捨DP框架來上色 粉刷房屋I_Paint House_Leetcode #256
Paint House 題目會給定一個成本陣列costs,分別代表每棟房屋粉刷成紅色、藍色、綠色的成本。 請問粉刷所有房屋的最小成本是多少,而且相鄰的房屋不可同一種顏色。
#
python
#
algorithm
#
leetcode
16
5
小松鼠
2024/06/12
化簡無所不在 用數列DP來解 給定公差的最長等差數列 Leetcode #1218
題目敘述 Longest Arithmetic Subsequence of Given Difference 給定一個整數陣列nums,請找出給定公差difference的最長的等差數列的長度是多少?
#
python
#
leetcode
#
algorithm
11
3
小松鼠
2024/06/12
化簡無所不在 用數列DP來解 給定公差的最長等差數列 Leetcode #1218
題目敘述 Longest Arithmetic Subsequence of Given Difference 給定一個整數陣列nums,請找出給定公差difference的最長的等差數列的長度是多少?
#
python
#
leetcode
#
algorithm
11
3
小松鼠
2024/06/12
用取捨DP來考高分 Solving Questions With Brainpower_Leetcode #2140
題目敘述 Solving Questions With Brainpower 給定一個測驗題陣列,每個欄位都是一個pair, 分別記錄測驗題做完可以得到的分數,和需要的冷卻時間 (也就是會有一段時間不能作答接下來的題目)。 請問在最佳的答題策略下,最多可以獲得多少分數?
#
python
#
leetcode
#
algorithm
11
4
小松鼠
2024/06/12
用取捨DP來考高分 Solving Questions With Brainpower_Leetcode #2140
題目敘述 Solving Questions With Brainpower 給定一個測驗題陣列,每個欄位都是一個pair, 分別記錄測驗題做完可以得到的分數,和需要的冷卻時間 (也就是會有一段時間不能作答接下來的題目)。 請問在最佳的答題策略下,最多可以獲得多少分數?
#
python
#
leetcode
#
algorithm
11
4
小松鼠
2024/06/10
用樹型DP思想來看 二元樹最大的區間路徑和 Binary Tree Max Path Sum_Leetcode #124
題目敘述 Binary Tree Maximum Path Sum 給定一個二元樹,請找出最大的區間路徑和是多少? 註: 區間路徑和 = 某個節點a -> 某個節點b的路徑節點值總和。
#
python
#
leetcode
#
algorithm
13
3
小松鼠
2024/06/10
用樹型DP思想來看 二元樹最大的區間路徑和 Binary Tree Max Path Sum_Leetcode #124
題目敘述 Binary Tree Maximum Path Sum 給定一個二元樹,請找出最大的區間路徑和是多少? 註: 區間路徑和 = 某個節點a -> 某個節點b的路徑節點值總和。
#
python
#
leetcode
#
algorithm
13
3
小松鼠
2024/06/10
化簡無所不在 用找零錢DP框架來解 組合數之和IV_Combinations Sum IV_Leetcode #377
題目敘述 Combination Sum IV 給定一個輸入陣列nums,和目標值target,從nums裡面挑數字去湊出總和 = target,數字可以重複挑選。 請問有多少排列數可以湊出target? 註: 排列數的意思就是位置不同代表兩種不同的方法數。
#
python
#
leetcode
#
algorithm
14
8
小松鼠
2024/06/10
化簡無所不在 用找零錢DP框架來解 組合數之和IV_Combinations Sum IV_Leetcode #377
題目敘述 Combination Sum IV 給定一個輸入陣列nums,和目標值target,從nums裡面挑數字去湊出總和 = target,數字可以重複挑選。 請問有多少排列數可以湊出target? 註: 排列數的意思就是位置不同代表兩種不同的方法數。
#
python
#
leetcode
#
algorithm
14
8
小松鼠
2024/06/09
舉一反三 用樹型DP思想來解 House Robbery III_Leetcode #337
題目敘述 House Robber III 題目會給我們一個二元樹, 二元樹裡的每個節點分別代表每棟房屋的價值,也就是房屋內有的現金數量。 題目敘述給的情境是假想盜賊要偷東西,限制是上下相鄰樓層的兩棟房屋不能一起偷,只能選擇其中一棟,否則就會觸發警報器。 請問盜賊可以得手的最大金額是多少?
#
python
#
leetcode
#
algorithm
14
3
小松鼠
2024/06/09
舉一反三 用樹型DP思想來解 House Robbery III_Leetcode #337
題目敘述 House Robber III 題目會給我們一個二元樹, 二元樹裡的每個節點分別代表每棟房屋的價值,也就是房屋內有的現金數量。 題目敘述給的情境是假想盜賊要偷東西,限制是上下相鄰樓層的兩棟房屋不能一起偷,只能選擇其中一棟,否則就會觸發警報器。 請問盜賊可以得手的最大金額是多少?
#
python
#
leetcode
#
algorithm
14
3
小松鼠
2024/06/09
用DP框架來思考 匹配目標字串的子序列 Distinct Subsequences_Leetcode #115
題目敘述 Distinct Subsequences 給定一個字串s和目標t,請問有多少個s的子序列可以完美匹配目標t ? 也就是說,有多少個s的子序列和目標t相等? 測試範例 Input: s = "rabbbit", t = "rabbit" Output: 3
#
python
#
leetcode
#
algorithm
8
2
小松鼠
2024/06/09
用DP框架來思考 匹配目標字串的子序列 Distinct Subsequences_Leetcode #115
題目敘述 Distinct Subsequences 給定一個字串s和目標t,請問有多少個s的子序列可以完美匹配目標t ? 也就是說,有多少個s的子序列和目標t相等? 測試範例 Input: s = "rabbbit", t = "rabbit" Output: 3
#
python
#
leetcode
#
algorithm
8
2
小松鼠
2024/06/09
用DP來精打細算 火車旅行支出的最小費用_Leetcode #983 最佳化DP應用
題目敘述 Minimum Cost For Tickets 題目會給定兩個陣列。 第一個是日期陣列days,代表外出旅遊的是哪幾天。 第二個是成本陣列costs,代表火車一日票、七日票、30日的月票的票價。 請問火車旅行支出的最小費用是多少?
#
python
#
leetcode
#
algorithm
17
16
小松鼠
2024/06/09
用DP來精打細算 火車旅行支出的最小費用_Leetcode #983 最佳化DP應用
題目敘述 Minimum Cost For Tickets 題目會給定兩個陣列。 第一個是日期陣列days,代表外出旅遊的是哪幾天。 第二個是成本陣列costs,代表火車一日票、七日票、30日的月票的票價。 請問火車旅行支出的最小費用是多少?
#
python
#
leetcode
#
algorithm
17
16
小松鼠
2024/06/09
化簡無所不在 用LCS的DP模型解 最長回文子序列 Longest Palindromic Subseq_LC#516
題目敘述 Longest Palindromic Subsequence 給定一個字串s,請找出字串s的最長回文子序列的長度。 註: 子序列 不要求一定要連續。 測試範例 Input: s = "bbbab" Output: 4
#
python
#
leetcode
#
algorithm
9
5
小松鼠
2024/06/09
化簡無所不在 用LCS的DP模型解 最長回文子序列 Longest Palindromic Subseq_LC#516
題目敘述 Longest Palindromic Subsequence 給定一個字串s,請找出字串s的最長回文子序列的長度。 註: 子序列 不要求一定要連續。 測試範例 Input: s = "bbbab" Output: 4
#
python
#
leetcode
#
algorithm
9
5
小松鼠
2024/06/09
物以群分 有幾個整除k的連續區間 Subarray Sums Divisible by K_Leetcode #974
題目敘述 Subarray Sums Divisible by K 給定一個整數陣列,請計算有幾個區間和能夠整除k的連續區間? 測試範例 Input: nums = [4,5,0,-2,-3,1], k = 5 Output: 7
#
python
#
leetcode
#
algorithm
8
1
小松鼠
2024/06/09
物以群分 有幾個整除k的連續區間 Subarray Sums Divisible by K_Leetcode #974
題目敘述 Subarray Sums Divisible by K 給定一個整數陣列,請計算有幾個區間和能夠整除k的連續區間? 測試範例 Input: nums = [4,5,0,-2,-3,1], k = 5 Output: 7
#
python
#
leetcode
#
algorithm
8
1
小松鼠
2024/06/08
用DP框架來思考 最長回文子字串 Longest Palindromic Substring_Leetcode #5
題目敘述 Longest Palindromic Substring 給定一個輸入字串s,請找出最長的回文子字串。 答案可能不只一個,回傳任何一個合法的答案皆可。
#
python
#
leetcode
#
algorithm
10
5
小松鼠
2024/06/08
用DP框架來思考 最長回文子字串 Longest Palindromic Substring_Leetcode #5
題目敘述 Longest Palindromic Substring 給定一個輸入字串s,請找出最長的回文子字串。 答案可能不只一個,回傳任何一個合法的答案皆可。
#
python
#
leetcode
#
algorithm
10
5
加入
全部
格子點DP
數列/子序列 DP
字串/區間 DP
最佳化/交易模擬DP
樹型DP
取捨DP
全部
格子點DP
數列/子序列 DP
字串/區間 DP
最佳化/交易模擬DP
樹型DP
取捨DP
全部類型
免費與付費
最新發佈
最新發佈
小松鼠
2024/09/13
♒成雙成對 子陣列的XOR query_XOR Queries of a Subarray_Leetcode #1310
給定一個整數陣列arr,和一串區間XOR請求queries。 請計算queries所請求的區間XOR值,並且以陣列的形式返回答案。
#
python
#
leetcode
#
algorithm
12
5
小松鼠
2024/09/13
♒成雙成對 子陣列的XOR query_XOR Queries of a Subarray_Leetcode #1310
給定一個整數陣列arr,和一串區間XOR請求queries。 請計算queries所請求的區間XOR值,並且以陣列的形式返回答案。
#
python
#
leetcode
#
algorithm
12
5
小松鼠
2024/08/27
🚗用圖論+DP來找 成功機率最高的路徑 Path w/ Max Probability_Leetcode #1514
Path with Maximum Probability 題目給定一個無向圖(雙向移動皆可), 提供每條邊的起終點,和每條邊對應的通過時的成功機率。 請問從起點start走到終點end的最高成功機率是多少? 如果完全沒有路徑可以抵達,則返回0。
#
python
#
leetcode
#
algorithm
6
8
小松鼠
2024/08/27
🚗用圖論+DP來找 成功機率最高的路徑 Path w/ Max Probability_Leetcode #1514
Path with Maximum Probability 題目給定一個無向圖(雙向移動皆可), 提供每條邊的起終點,和每條邊對應的通過時的成功機率。 請問從起點start走到終點end的最高成功機率是多少? 如果完全沒有路徑可以抵達,則返回0。
#
python
#
leetcode
#
algorithm
6
8
小松鼠
2024/08/21
用字串DP來操作印表機 奇怪的印表機_Leetcode #664
題目敘述 664. Strange Printer 有一台奇怪的印表機, 每次操作只能連續印同樣的字母,但是列印的長度可以自由控制。 而且,印刷的時候,可以蓋過去舊的字元。 (這邊當然不合常理,讀者可以理解成塗了立可帶再蓋過去的情境) 給定一個輸入字串s,請問最少需要幾次操作,才能印出字串s?
#
python
#
leetcode
#
algorithm
8
2
小松鼠
2024/08/21
用字串DP來操作印表機 奇怪的印表機_Leetcode #664
題目敘述 664. Strange Printer 有一台奇怪的印表機, 每次操作只能連續印同樣的字母,但是列印的長度可以自由控制。 而且,印刷的時候,可以蓋過去舊的字元。 (這邊當然不合常理,讀者可以理解成塗了立可帶再蓋過去的情境) 給定一個輸入字串s,請問最少需要幾次操作,才能印出字串s?
#
python
#
leetcode
#
algorithm
8
2
小松鼠
2024/08/20
用DP來玩遊戲 石頭遊戲 III_Stone Game III_Leetcode #1406
題目敘述 1406. Stone Game III Alice 和 Bob 輪流玩取石頭的遊戲。 輸入陣列stoneValue 代表每顆石頭對應的價值。 規則如下: 每個人每回合可以從剩餘的石頭,從前面拿一顆、兩顆、或三顆石頭。 兩個人輪流交替拿。Alice先手,第一回合Alice
#
python
#
game
#
stonegame
9
2
小松鼠
2024/08/20
用DP來玩遊戲 石頭遊戲 III_Stone Game III_Leetcode #1406
題目敘述 1406. Stone Game III Alice 和 Bob 輪流玩取石頭的遊戲。 輸入陣列stoneValue 代表每顆石頭對應的價值。 規則如下: 每個人每回合可以從剩餘的石頭,從前面拿一顆、兩顆、或三顆石頭。 兩個人輪流交替拿。Alice先手,第一回合Alice
#
python
#
game
#
stonegame
9
2
小松鼠
2024/08/19
字串DP: 用最少的操作次數生成字串_2 Keys Keyboard_Leetcode #650
題目敘述 Leetcode: 650. 2 Keys Keyboard 一開始初始化的時候,記事本上只有一個字元'A'。 只允許下列兩種操作 複製目前記事本上的整個字串。 貼上之前複製的內容,串接在尾端。 請問,最少需要幾個操作, 才能製造出內容都是 "AAA...A",長度為n的字串?
#
python
#
leetcode
#
algorithm
6
2
小松鼠
2024/08/19
字串DP: 用最少的操作次數生成字串_2 Keys Keyboard_Leetcode #650
題目敘述 Leetcode: 650. 2 Keys Keyboard 一開始初始化的時候,記事本上只有一個字元'A'。 只允許下列兩種操作 複製目前記事本上的整個字串。 貼上之前複製的內容,串接在尾端。 請問,最少需要幾個操作, 才能製造出內容都是 "AAA...A",長度為n的字串?
#
python
#
leetcode
#
algorithm
6
2
小松鼠
2024/08/18
數列DP應用: Ugly Number II _Leetcode #264
題目敘述: 264. Ugly Number II 定義Ugly number序列是質因數只有2, 3, 5的正整數數列。 也就是說 x = 2^i * 3^j * 5^k, where i >= 0, j >= 0, k >= 0 請計算第n項的Ugly number 等於多少?
#
python
#
leetcode
#
algorithm
7
5
小松鼠
2024/08/18
數列DP應用: Ugly Number II _Leetcode #264
題目敘述: 264. Ugly Number II 定義Ugly number序列是質因數只有2, 3, 5的正整數數列。 也就是說 x = 2^i * 3^j * 5^k, where i >= 0, j >= 0, k >= 0 請計算第n項的Ugly number 等於多少?
#
python
#
leetcode
#
algorithm
7
5
小松鼠
2024/07/30
用DP來精打細算 切割木條的最小成本 Min Cost to Cut a Stick_Leetcode #1547
給定木板的長度和切割點位置,找到最小總切割成本。透過DP動態規劃和區間DP框架,定義DP狀態並推導出最小切割成本的遞迴關係式。複雜度分析為時間複雜度O(n^3)和空間複雜度O(n^2)。關鍵知識點在於挖掘切割問條的共通模式,透過範例和圖解輔助思考。
#
python
#
leetcode
#
algorithm
10
1
小松鼠
2024/07/30
用DP來精打細算 切割木條的最小成本 Min Cost to Cut a Stick_Leetcode #1547
給定木板的長度和切割點位置,找到最小總切割成本。透過DP動態規劃和區間DP框架,定義DP狀態並推導出最小切割成本的遞迴關係式。複雜度分析為時間複雜度O(n^3)和空間複雜度O(n^2)。關鍵知識點在於挖掘切割問條的共通模式,透過範例和圖解輔助思考。
#
python
#
leetcode
#
algorithm
10
1
小松鼠
2024/07/28
圖論+DP: 字串轉換的最小成本 Min Cost to Convert String I_Leetcode #2976
題目敘述: Minimum Cost to Convert String I 給定字元轉換映射表original, changes和對硬的成本陣列cost。 請問字串source轉換到字串destination的最小成本是多少? 如果無解,請返回-1 如果有解,請返回整體的轉換最小成本。
#
python
#
leetcode
#
algorithm
13
5
小松鼠
2024/07/28
圖論+DP: 字串轉換的最小成本 Min Cost to Convert String I_Leetcode #2976
題目敘述: Minimum Cost to Convert String I 給定字元轉換映射表original, changes和對硬的成本陣列cost。 請問字串source轉換到字串destination的最小成本是多少? 如果無解,請返回-1 如果有解,請返回整體的轉換最小成本。
#
python
#
leetcode
#
algorithm
13
5
小松鼠
2024/06/14
用格子點DP來解 三角形最小成本下降路徑 Triangle_Leetcode #120
題目敘述 Triangle 題目會給我們一個三角形的二維陣列triangle ,每個元素分別代表每個格子的成本,請問我們從最頂端到底部的下墜路徑的最小成本總和是多少? 每次下墜到下一排的時候,可以有兩種選擇: 1.往左下方的格子點移動。 2.往右下方的格子點移動。 測試範例 Examp
#
python
#
leetcode
#
algorithm
14
3
小松鼠
2024/06/14
用格子點DP來解 三角形最小成本下降路徑 Triangle_Leetcode #120
題目敘述 Triangle 題目會給我們一個三角形的二維陣列triangle ,每個元素分別代表每個格子的成本,請問我們從最頂端到底部的下墜路徑的最小成本總和是多少? 每次下墜到下一排的時候,可以有兩種選擇: 1.往左下方的格子點移動。 2.往右下方的格子點移動。 測試範例 Examp
#
python
#
leetcode
#
algorithm
14
3
小松鼠
2024/06/12
用取捨DP框架來上色 粉刷房屋I_Paint House_Leetcode #256
Paint House 題目會給定一個成本陣列costs,分別代表每棟房屋粉刷成紅色、藍色、綠色的成本。 請問粉刷所有房屋的最小成本是多少,而且相鄰的房屋不可同一種顏色。
#
python
#
algorithm
#
leetcode
16
5
小松鼠
2024/06/12
用取捨DP框架來上色 粉刷房屋I_Paint House_Leetcode #256
Paint House 題目會給定一個成本陣列costs,分別代表每棟房屋粉刷成紅色、藍色、綠色的成本。 請問粉刷所有房屋的最小成本是多少,而且相鄰的房屋不可同一種顏色。
#
python
#
algorithm
#
leetcode
16
5
小松鼠
2024/06/12
化簡無所不在 用數列DP來解 給定公差的最長等差數列 Leetcode #1218
題目敘述 Longest Arithmetic Subsequence of Given Difference 給定一個整數陣列nums,請找出給定公差difference的最長的等差數列的長度是多少?
#
python
#
leetcode
#
algorithm
11
3
小松鼠
2024/06/12
化簡無所不在 用數列DP來解 給定公差的最長等差數列 Leetcode #1218
題目敘述 Longest Arithmetic Subsequence of Given Difference 給定一個整數陣列nums,請找出給定公差difference的最長的等差數列的長度是多少?
#
python
#
leetcode
#
algorithm
11
3
小松鼠
2024/06/12
用取捨DP來考高分 Solving Questions With Brainpower_Leetcode #2140
題目敘述 Solving Questions With Brainpower 給定一個測驗題陣列,每個欄位都是一個pair, 分別記錄測驗題做完可以得到的分數,和需要的冷卻時間 (也就是會有一段時間不能作答接下來的題目)。 請問在最佳的答題策略下,最多可以獲得多少分數?
#
python
#
leetcode
#
algorithm
11
4
小松鼠
2024/06/12
用取捨DP來考高分 Solving Questions With Brainpower_Leetcode #2140
題目敘述 Solving Questions With Brainpower 給定一個測驗題陣列,每個欄位都是一個pair, 分別記錄測驗題做完可以得到的分數,和需要的冷卻時間 (也就是會有一段時間不能作答接下來的題目)。 請問在最佳的答題策略下,最多可以獲得多少分數?
#
python
#
leetcode
#
algorithm
11
4
小松鼠
2024/06/10
用樹型DP思想來看 二元樹最大的區間路徑和 Binary Tree Max Path Sum_Leetcode #124
題目敘述 Binary Tree Maximum Path Sum 給定一個二元樹,請找出最大的區間路徑和是多少? 註: 區間路徑和 = 某個節點a -> 某個節點b的路徑節點值總和。
#
python
#
leetcode
#
algorithm
13
3
小松鼠
2024/06/10
用樹型DP思想來看 二元樹最大的區間路徑和 Binary Tree Max Path Sum_Leetcode #124
題目敘述 Binary Tree Maximum Path Sum 給定一個二元樹,請找出最大的區間路徑和是多少? 註: 區間路徑和 = 某個節點a -> 某個節點b的路徑節點值總和。
#
python
#
leetcode
#
algorithm
13
3
小松鼠
2024/06/10
化簡無所不在 用找零錢DP框架來解 組合數之和IV_Combinations Sum IV_Leetcode #377
題目敘述 Combination Sum IV 給定一個輸入陣列nums,和目標值target,從nums裡面挑數字去湊出總和 = target,數字可以重複挑選。 請問有多少排列數可以湊出target? 註: 排列數的意思就是位置不同代表兩種不同的方法數。
#
python
#
leetcode
#
algorithm
14
8
小松鼠
2024/06/10
化簡無所不在 用找零錢DP框架來解 組合數之和IV_Combinations Sum IV_Leetcode #377
題目敘述 Combination Sum IV 給定一個輸入陣列nums,和目標值target,從nums裡面挑數字去湊出總和 = target,數字可以重複挑選。 請問有多少排列數可以湊出target? 註: 排列數的意思就是位置不同代表兩種不同的方法數。
#
python
#
leetcode
#
algorithm
14
8
小松鼠
2024/06/09
舉一反三 用樹型DP思想來解 House Robbery III_Leetcode #337
題目敘述 House Robber III 題目會給我們一個二元樹, 二元樹裡的每個節點分別代表每棟房屋的價值,也就是房屋內有的現金數量。 題目敘述給的情境是假想盜賊要偷東西,限制是上下相鄰樓層的兩棟房屋不能一起偷,只能選擇其中一棟,否則就會觸發警報器。 請問盜賊可以得手的最大金額是多少?
#
python
#
leetcode
#
algorithm
14
3
小松鼠
2024/06/09
舉一反三 用樹型DP思想來解 House Robbery III_Leetcode #337
題目敘述 House Robber III 題目會給我們一個二元樹, 二元樹裡的每個節點分別代表每棟房屋的價值,也就是房屋內有的現金數量。 題目敘述給的情境是假想盜賊要偷東西,限制是上下相鄰樓層的兩棟房屋不能一起偷,只能選擇其中一棟,否則就會觸發警報器。 請問盜賊可以得手的最大金額是多少?
#
python
#
leetcode
#
algorithm
14
3
小松鼠
2024/06/09
用DP框架來思考 匹配目標字串的子序列 Distinct Subsequences_Leetcode #115
題目敘述 Distinct Subsequences 給定一個字串s和目標t,請問有多少個s的子序列可以完美匹配目標t ? 也就是說,有多少個s的子序列和目標t相等? 測試範例 Input: s = "rabbbit", t = "rabbit" Output: 3
#
python
#
leetcode
#
algorithm
8
2
小松鼠
2024/06/09
用DP框架來思考 匹配目標字串的子序列 Distinct Subsequences_Leetcode #115
題目敘述 Distinct Subsequences 給定一個字串s和目標t,請問有多少個s的子序列可以完美匹配目標t ? 也就是說,有多少個s的子序列和目標t相等? 測試範例 Input: s = "rabbbit", t = "rabbit" Output: 3
#
python
#
leetcode
#
algorithm
8
2
小松鼠
2024/06/09
用DP來精打細算 火車旅行支出的最小費用_Leetcode #983 最佳化DP應用
題目敘述 Minimum Cost For Tickets 題目會給定兩個陣列。 第一個是日期陣列days,代表外出旅遊的是哪幾天。 第二個是成本陣列costs,代表火車一日票、七日票、30日的月票的票價。 請問火車旅行支出的最小費用是多少?
#
python
#
leetcode
#
algorithm
17
16
小松鼠
2024/06/09
用DP來精打細算 火車旅行支出的最小費用_Leetcode #983 最佳化DP應用
題目敘述 Minimum Cost For Tickets 題目會給定兩個陣列。 第一個是日期陣列days,代表外出旅遊的是哪幾天。 第二個是成本陣列costs,代表火車一日票、七日票、30日的月票的票價。 請問火車旅行支出的最小費用是多少?
#
python
#
leetcode
#
algorithm
17
16
小松鼠
2024/06/09
化簡無所不在 用LCS的DP模型解 最長回文子序列 Longest Palindromic Subseq_LC#516
題目敘述 Longest Palindromic Subsequence 給定一個字串s,請找出字串s的最長回文子序列的長度。 註: 子序列 不要求一定要連續。 測試範例 Input: s = "bbbab" Output: 4
#
python
#
leetcode
#
algorithm
9
5
小松鼠
2024/06/09
化簡無所不在 用LCS的DP模型解 最長回文子序列 Longest Palindromic Subseq_LC#516
題目敘述 Longest Palindromic Subsequence 給定一個字串s,請找出字串s的最長回文子序列的長度。 註: 子序列 不要求一定要連續。 測試範例 Input: s = "bbbab" Output: 4
#
python
#
leetcode
#
algorithm
9
5
小松鼠
2024/06/09
物以群分 有幾個整除k的連續區間 Subarray Sums Divisible by K_Leetcode #974
題目敘述 Subarray Sums Divisible by K 給定一個整數陣列,請計算有幾個區間和能夠整除k的連續區間? 測試範例 Input: nums = [4,5,0,-2,-3,1], k = 5 Output: 7
#
python
#
leetcode
#
algorithm
8
1
小松鼠
2024/06/09
物以群分 有幾個整除k的連續區間 Subarray Sums Divisible by K_Leetcode #974
題目敘述 Subarray Sums Divisible by K 給定一個整數陣列,請計算有幾個區間和能夠整除k的連續區間? 測試範例 Input: nums = [4,5,0,-2,-3,1], k = 5 Output: 7
#
python
#
leetcode
#
algorithm
8
1
小松鼠
2024/06/08
用DP框架來思考 最長回文子字串 Longest Palindromic Substring_Leetcode #5
題目敘述 Longest Palindromic Substring 給定一個輸入字串s,請找出最長的回文子字串。 答案可能不只一個,回傳任何一個合法的答案皆可。
#
python
#
leetcode
#
algorithm
10
5
小松鼠
2024/06/08
用DP框架來思考 最長回文子字串 Longest Palindromic Substring_Leetcode #5
題目敘述 Longest Palindromic Substring 給定一個輸入字串s,請找出最長的回文子字串。 答案可能不只一個,回傳任何一個合法的答案皆可。
#
python
#
leetcode
#
algorithm
10
5