大家好，我是Carl。

這篇來給大家講一講解決動態規劃的方法論-動規五部曲。

先上一份動態規劃的刷題大綱：

我這裡整理出一份

演算法PD

F，pdf中不僅有刷題大綱、刷題順序，還有詳細圖解，每一本pdf釋出之後都廣受好評先，PDF中攻擊30w字詳細圖解了 100多道力扣上的經典題目，上圖：

無論現在要不要學習演算法，先去下載看看吧，想進大廠一定需要這個！

動態規劃的解題步驟

做動規題目的時候，很多同學會陷入一個誤區，就是以為把狀態轉移公式背下來，照葫蘆畫瓢改改，就開始寫程式碼，甚至把題目AC之後，都不太清楚dp［i］表示的是什麼。

這就是一種朦朧的狀態，然後就把題給過了，遇到稍稍難一點的，可能直接就不會了，然後看題解，然後繼續照葫蘆畫瓢陷入這種惡性迴圈中

。

狀態轉移公式

（遞推公式）是很重要，但動規不僅僅只有遞推公式。

對於動態規劃問題，我將拆解為如下五步曲，這五步都搞清楚了，才能說把動態規劃真的掌握了！

確定dp陣列（dp table）以及下標的含義

確定遞推公式

dp陣列如何初始化

確定遍歷順序

舉例推導dp陣列

一些同學可能想為什麼要先確定遞推公式，然後在考慮初始化呢？

因為一些情況是遞推公式決定了dp陣列要如何初始化！

後面的講解中我都是圍繞著這五點來進行講解。

可能刷過動態規劃題目的同學可能都知道遞推公式的重要性，感覺確定了遞推公式這道題目就解出來了。

其實 確定遞推公式 僅僅是解題裡的一步而已！

一些同學知道遞推公式，但搞不清楚dp陣列應該如何初始化，或者正確的遍歷順序，以至於記下來公式，但寫的程式怎麼改都通過不了。

後序的講解的大家就會慢慢感受到這五步的重要性了。

動態規劃應該如何debug

相信動規的題目，很大部分同學都是這樣做的。

看一下題解，感覺看懂了，然後照葫蘆畫瓢，如果能正好畫對了，萬事大吉，一旦要是沒透過，就怎麼改都通過不了，對 dp陣列的初始化，

遞迴公式

，遍歷順序，處於一種黑盒的理解狀態。

寫動規題目，程式碼出問題很正常！

找問題的最好方式就是把dp陣列打印出來，看看究竟是不是按照自己思路推導的！

一些同學對於dp的學習是黑盒的狀態，就是不清楚dp陣列的含義，不懂為什麼這麼初始化，遞推公式背下來了，遍歷順序靠習慣就是這麼寫的，然後一鼓作氣寫出程式碼，如果程式碼能透過萬事大吉，通過不了的話就憑感覺改一改。

這是一個很不好的習慣！

做動規的題目，寫程式碼之前一定要把狀態轉移在dp陣列的上具體情況模擬一遍，心中有數，確定最後推出的是想要的結果

。

然後再寫程式碼，如果程式碼沒透過就列印dp陣列，看看是不是和自己預先推導的哪裡不一樣。

如果打印出來和自己預先模擬推導是一樣的，那麼就是自己的遞迴公式、初始化或者

遍歷

順序有問題了。

如果和自己預先模擬推導的不一樣，那麼就是程式碼實現細節有問題。

這樣才是一個完整的思考過程，而不是一旦程式碼出問題，就毫無頭緒的東改改西改改，最後過不了，或者說是稀裡糊塗的過了

。

這也是我為什麼在動規五步曲裡強調推導dp陣列的重要性。

舉個例子：在「程式碼隨想錄」刷題小分隊微信群裡，一些同學可能程式碼通過不了，會把程式碼拋到討論群裡問：我這裡程式碼都已經和題解一模一樣了，為什麼通過不了呢？

發出這樣的問題之前，其實可以自己先思考這三個問題：

這道題目我舉例推導狀態轉移公式了麼？

我列印dp陣列的日誌了麼？

打印出來了dp陣列和我想的一樣麼？

如果這靈魂三問自己都做到了，基本上這道題目也就解決了

，或者更清晰的知道自己究竟是哪一點不明白，是狀態轉移不明白，還是實現程式碼不知道該怎麼寫，還是不理解遍歷dp陣列的順序。

然後在問問題，目的性就很強了，群裡的小夥伴也可以快速知道提問者的疑惑了。

注意這裡不是說不讓大家問問題哈， 而是說問問題之前要有自己的思考，問題要問到點子上！

大家工作之後就會發現，特別是大廠，問問題是一個專業活，是的，問問題也要體現出專業！

如果問同事很不專業的問題，同事們會懶的回答，領導也會認為你缺乏思考能力，這對

職場

發展是很不利的。

所以大家在刷題的時候，就鍛鍊自己養成專業提問的好習慣。

關於動態規劃的疑惑

還有不少同學對動規的理解是：遞推公式是才是最難最重要的，只要想出遞迴公式，其他都好辦。

其實這麼想的同學基本對動規理解的不到位的

。

動規五部曲裡，哪一部沒想清楚，這道題目基本就做不出來，即使做出來了也沒有想清楚，而是朦朦朧朧的就把題目過了。

如果想不清楚dp陣列的具體含義，遞迴公式從何談起，甚至初始化的時候就寫錯了。

例如

動態規劃：不同路徑還不夠，要有障礙！

在這道題目中，

初始化

才是重頭戲

如果看過揹包系列，特別是完全揹包，那麼兩層for迴圈先後順序絕對可以搞懵很多人，反而遞迴公式是簡單的。

至於推導dp陣列的重要性，動規專題裡幾乎每篇Carl都反覆強調，當程式結果不對的時候，一定要自己推導公式，看看和程式列印的日誌是否一樣。

動態規劃刷題路線

這裡給出我總結動態規劃刷題路線大綱：

按照這個刷題大綱，都有我寫的詳細題解，每一篇題解都是精品，大家一篇一篇按照順序學習就可以了，慢慢就會發現動規五部曲的重要性！

關於動態規劃，你該瞭解這些！

動態規劃：斐波那契數

動態規劃：爬樓梯

動態規劃：使用最小花費爬樓梯

本週小結！（動態規劃系列一）

動態規劃：不同路徑

動態規劃：不同路徑還不夠，要有障礙！

動態規劃：整數拆分，你要怎麼拆？

動態規劃：不同的二叉搜尋樹

本週小結！（動態規劃系列二）

揹包問題系列：

動態規劃：關於01揹包問題，你該瞭解這些！

動態規劃：關於01揹包問題，你該瞭解這些！（滾動陣列）

動態規劃：分割等和子集可以用01揹包！

動態規劃：最後一塊石頭的重量 II

本週小結！（動態規劃系列三）

動態規劃：目標和！

動態規劃：一和零！

動態規劃：關於完全揹包，你該瞭解這些！

動態規劃：給你一些零錢，你要怎麼湊？

本週小結！（動態規劃系列四）

動態規劃：Carl稱它為排列總和！

動態規劃：以前我沒得選，現在我選擇再爬一次！

動態規劃： 給我個機會，我再兌換一次零錢

動態規劃：一樣的套路，再求一次完全平方數

本週小結！（動態規劃系列五）

動態規劃：單詞拆分

動態規劃：關於多重揹包，你該瞭解這些！

聽說揹包問題很難？ 這篇總結篇來拯救你了

打家劫舍系列：

動態規劃：開始打家劫舍！

動態規劃：繼續打家劫舍！

動態規劃：還要打家劫舍！

股票系列：

動態規劃：買賣股票的最佳時機

動態規劃：本週我們都講了這些（系列六）

動態規劃：買賣股票的最佳時機II

動態規劃：買賣股票的最佳時機III

動態規劃：買賣股票的最佳時機IV

動態規劃：最佳買賣股票時機含冷凍期

動態規劃：本週我們都講了這些（系列七）

動態規劃：買賣股票的最佳時機含手續費

動態規劃：股票系列總結篇

子序列系列：

動態規劃：最長遞增子序列

動態規劃：最長連續遞增序列

動態規劃：最長重複子陣列

動態規劃：最長公共子序列

動態規劃：本週我們都講了這些（系列八）

動態規劃：不相交的線

動態規劃：最大子序和

動態規劃：判斷子序列

動態規劃：不同的子序列

動態規劃：兩個字串的刪除操作

動態規劃：本週我們都講了這些（系列十）

動態規劃：編輯距離

為了絕殺編輯距離，我做了三步鋪墊，你都知道麼？

動態規劃：迴文子串

動態規劃：最長迴文子序列

動態規劃總結篇

同時我將刷題攻略整理在Github上，瞬間登上了 Github全球熱榜，上榜了……

github 專案截圖：

這個專案裡面有200道經典演算法題目刷題順序、配有60w字的詳細圖解，常用演算法模板總結，以及難點影片講解，按照list一道一道刷就可以了！

去看看吧，這個Github演算法學習專案會驚豔到你！

可以在B站上關注我，上面有很多演算法的講解影片。

碼字不已，希望對你有所幫助！

@程式碼隨想錄

點個贊就是對我最大的鼓勵，筆芯~