DP
#DP含有「DP」共 67 篇內容
全部內容
發佈日期由新至舊
用格子點DP來解 三角形最小成本下降路徑 Triangle_Leetcode #120題目敘述 Triangle
題目會給我們一個三角形的二維陣列triangle ，每個元素分別代表每個格子的成本，請問我們從最頂端到底部的下墜路徑的最小成本總和是多少?
每次下墜到下一排的時候，可以有兩種選擇:
1.往左下方的格子點移動。
2.往右下方的格子點移動。
測試範例
Examp
發佈在
小松鼠的演算法樂園
2024-06-14
12
用取捨DP框架來上色 粉刷房屋I_Paint House_Leetcode #256Paint House
題目會給定一個成本陣列costs，分別代表每棟房屋粉刷成紅色、藍色、綠色的成本。
請問粉刷所有房屋的最小成本是多少，而且相鄰的房屋不可同一種顏色。
發佈在
小松鼠的演算法樂園
2024-06-12
14
化簡無所不在 用數列DP來解 給定公差的最長等差數列 Leetcode #1218題目敘述 Longest Arithmetic Subsequence of Given Difference
給定一個整數陣列nums，請找出給定公差difference的最長的等差數列的長度是多少?
發佈在
小松鼠的演算法樂園
2024-06-12
10
用取捨DP來考高分 Solving Questions With Brainpower_Leetcode #2140題目敘述 Solving Questions With Brainpower
給定一個測驗題陣列，每個欄位都是一個pair，
分別記錄測驗題做完可以得到的分數，和需要的冷卻時間
(也就是會有一段時間不能作答接下來的題目)。
請問在最佳的答題策略下，最多可以獲得多少分數?
發佈在
小松鼠的演算法樂園
2024-06-12
9
化簡無所不在 用找零錢DP框架來解 組合數之和IV_Combinations Sum IV_Leetcode #377題目敘述 Combination Sum IV
給定一個輸入陣列nums，和目標值target，從nums裡面挑數字去湊出總和 = target，數字可以重複挑選。
請問有多少排列數可以湊出target？
註: 排列數的意思就是位置不同代表兩種不同的方法數。
發佈在
小松鼠的演算法樂園
2024-06-10
13
舉一反三 用樹型DP思想來解 House Robbery III_Leetcode #337題目敘述 House Robber III
題目會給我們一個二元樹，
二元樹裡的每個節點分別代表每棟房屋的價值，也就是房屋內有的現金數量。
題目敘述給的情境是假想盜賊要偷東西，限制是上下相鄰樓層的兩棟房屋不能一起偷，只能選擇其中一棟，否則就會觸發警報器。
請問盜賊可以得手的最大金額是多少?
發佈在
小松鼠的演算法樂園
2024-06-09
13
用DP框架來思考 匹配目標字串的子序列 Distinct Subsequences_Leetcode #115題目敘述 Distinct Subsequences
給定一個字串s和目標t，請問有多少個s的子序列可以完美匹配目標t ?
也就是說，有多少個s的子序列和目標t相等?
測試範例
Input: s = "rabbbit", t = "rabbit"
Output: 3
發佈在
小松鼠的演算法樂園
2024-06-09
7
用DP來精打細算 火車旅行支出的最小費用_Leetcode #983 最佳化DP應用題目敘述 Minimum Cost For Tickets
題目會給定兩個陣列。
第一個是日期陣列days，代表外出旅遊的是哪幾天。
第二個是成本陣列costs，代表火車一日票、七日票、30日的月票的票價。
請問火車旅行支出的最小費用是多少？
發佈在
小松鼠的演算法樂園
2024-06-09
16
化簡無所不在 用LCS的DP模型解 最長回文子序列 Longest Palindromic Subseq_LC#516題目敘述 Longest Palindromic Subsequence
給定一個字串s，請找出字串s的最長回文子序列的長度。
註: 子序列 不要求一定要連續。
測試範例
Input: s = "bbbab"
Output: 4
發佈在
小松鼠的演算法樂園
2024-06-09
8
物以群分 有幾個整除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
發佈在
小松鼠的演算法樂園
2024-06-09
7