這題也是滿經典的DP動態規劃教學案例和題目，就順便複習一下吧。

題目敘述

題目會給我們兩個字串text1, text2。

要求我們找出兩個字串的最長共同子序列，並且返回最長共同子序列的長度。

如果彼此沒有共同子序列，則返回0。


題目的原文敘述


測試範例

Example 1:

In

學習

職場

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

軟體開發

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

小松鼠的演算法樂園

DP經典應用: 找出 最長共同子序列的長度 LCS_Leetcode #1143_Leetcode 精選75題解析

今天再來看一題入門的2D DP題目: 巴斯卡三角形

再次複習Dynamic programming的解題框架，可分為三大步驟
1.定義狀態 [我在哪裡]
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
3. 釐清初始狀態(也可以說是遞

職場產業

DP動態規劃 深入淺出 以Pascal Triangle 巴斯卡三角形 為例_Leetcode #118

題目敘述
題目會給定我們一個字串s，和一組字庫wordDict。
問我們能不能透過字串串接的方式，從字庫裡面的字拼成原本的字串s?

可以的話，返回True。

無解的話，返回False。

註:

題目還允許重複使用字庫裡面的字去串接。
 

創作

一魚n吃 用DP來進行字串拆分配對 Word Break_Leetcode #139

題目敘述 Minimum Cost For Tickets

題目會給定兩個陣列。
第一個是日期陣列days，代表外出旅遊的是哪幾天。
第二個是成本陣列costs，代表火車一日票、七日票、30日的月票的票價。

請問火車旅行支出的最小費用是多少？


國際

文化生活

旅行美食

用DP來精打細算 火車旅行支出的最小費用_Leetcode #983 最佳化DP應用

題目會給我們一個輸入陣列candidates，和一個目標值 target
問我們，從canditdates裡面重複挑選，可以湊出總和為target目標值的組合數有幾種?

在此，我們將使用找零錢II的DP模型和化簡的技巧來解題。

投資理財

一魚多吃 用找零錢II的DP模型來解 Combination Sum_Leetcode #39

題目敘述

題目會給我們泰伯納西數列的一般項和初始條件，要求我們實現找出第n項的function。
def tribonacci(self, n: int):

泰伯納西數列的一般項: Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

泰伯納西數列的初始條件: T0 = 0,

活用DP: 泰伯納西數列的第n項 Leetcode #1137_精選75題

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



音樂藝文

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

題目敘述 Triangle

題目會給我們一個三角形的二維陣列triangle ，每個元素分別代表每個格子的成本，請問我們從最頂端到底部的下墜路徑的最小成本總和是多少?

每次下墜到下一排的時候，可以有兩種選擇:

1.往左下方的格子點移動。

2.往右下方的格子點移動。


測試範例

Examp

用格子點DP來解 三角形最小成本下降路徑 Triangle_Leetcode #120

這篇文章，會帶著大家複習以前學過的FSM+DP框架，
並且以有限狀態機 + DP狀態轉移的概念為核心，

貫穿一些相關聯最佳股票買賣系列的題目，
透過框架複現來幫助讀者理解這個實用的演算法框架。


基本的FSM + DP 框架，配合交易邏輯。



針對每一天，其實歸根究柢只有兩種狀態。

第一種

閱讀書評

合縱連橫: 從DP框架理解 最佳股票買賣系列題 的背後本質

Coin Change + DP 策略_Leetcode 面試題 上機考 題目 詳細解說

DP動態規劃 深入淺出 以Coin change最精簡找零 為例

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

親子與教育

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

演算法映射化簡的核心觀念

在面對新題目的時候，除了重頭想一個新的演算法之外；
還有另一個方法，想看看有沒有核心觀念彼此相同的問題與演算法，
如果有，就可以把新的題目映射化簡到已知解法的問題，用已知的演算法去解開。

接著，我們會介紹幾個範例，並且使用映射化簡的技巧來解題，透過化

化繁為簡: 映射化簡的演算法技巧

動態規劃Dynamic Programming其實是
一種泛用的演算法思考方式與演算法建構框架。

動態規劃並不拘束於只能解課本上特定的的範例題。

只要我們能找出DP狀態定義、DP遞迴結構、初始條件(終止條件)，就能適用動態規劃來解題，以數學的形式表達，並且在紙筆上或者電腦上、計算機上計算

究竟什麼是 動態規劃DP?

以Leetcode國際版官方精選DP動態規劃測驗題為大綱
以獨門的 DP三段式框架 和 化簡技巧 為輔
幫助讀者熟練DP框架與常見的DP演算法模板

DP動態規劃特訓班

目前尚無內容

DP動態規劃 特訓班

目前尚無內容

DP動態規劃特訓班