Paint House
題目會給定一個成本陣列costs，分別代表每棟房屋粉刷成紅色、藍色、綠色的成本。
請問粉刷所有房屋的最小成本是多少，而且相鄰的房屋不可同一種顏色。



學習

職場

音樂藝文

以行動支持創作者！付費即可解鎖

軟體開發

由有業界實戰經驗的演算法工程師，
手把手教你建立解題的框架，
一步步寫出高效、清晰易懂的解題答案。
著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。
深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。
在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。

小松鼠的演算法樂園

用取捨DP框架來上色 粉刷房屋I_Paint House_Leetcode #256

題目敘述 Combination Sum IV
給定一個輸入陣列nums，和目標值target，從nums裡面挑數字去湊出總和 = target，數字可以重複挑選。

請問有多少排列數可以湊出target？

註: 排列數的意思就是位置不同代表兩種不同的方法數。



投資理財

化簡無所不在 用找零錢DP框架來解 組合數之和IV_Combinations Sum IV_Leetcode #377

題目敘述 Distinct Subsequences

給定一個字串s和目標t，請問有多少個s的子序列可以完美匹配目標t ?

也就是說，有多少個s的子序列和目標t相等?


測試範例

Input: s = "rabbbit", t = "rabbit"
Output: 3

用DP框架來思考 匹配目標字串的子序列 Distinct Subsequences_Leetcode #115

題目敘述 Longest Palindromic Subsequence

給定一個字串s，請找出字串s的最長回文子序列的長度。

註: 子序列 不要求一定要連續。


測試範例

Input: s = "bbbab"
Output: 4


創作

文化生活


化簡無所不在 用LCS的DP模型解 最長回文子序列 Longest Palindromic Subseq_LC#516

題目敘述 Longest Palindromic Substring

給定一個輸入字串s，請找出最長的回文子字串。

答案可能不只一個，回傳任何一個合法的答案皆可。


親子與教育

用DP框架來思考 最長回文子字串 Longest Palindromic Substring_Leetcode #5

Minimum Path Sum

給定一個矩陣，每個格子點代表經過的對應成本。
每回合可以往右移動一格或往下移動一格。

請問從起點左上角 走到 終點右下角的最小路徑成本總和是多少?



用DP框架來思考 Minimum Path Sum 最小路徑成本總和_Leetcode #64

給定一個整數陣列nums，請找出等最長差數列的長度是多少?


用DP框架來思考 最長的等差數列Longest Arithmetic Subsequence_Leetcode#1027

給定一個輸入陣列，計算最長遞增子序列的總數。本題和Longest Common Subsequence相似，需要設定一個計數器，記錄最長遞增子序列的數量。透過DP模型的化簡方式來解決問題。時間複雜度為O(n^2)，空間複雜度為O(n)。主要使用回頭看的技巧，找出比較小的元素去延伸遞增子序列的長度。

化簡無所不在 用LIS的DP模型解Num of Longest Increasing Subseq._LC#673

DP特訓班的分類目錄
與 推薦的學習、練習順序

DP演算法框架 與 推薦的DP學習路徑 (持續更新中)

題目敘述

給定一個正整數n，請找出最少用幾個完全平方數，可以讓他們的總和為n?

例如 n=12，最少用3個完全平方數就可讓他們的總和為n，因為12 = 4 + 4 + 4


題目的原文敘述


測試範例

Example 1:

Input: n = 12
Output: 3
Explanat

多維DP