為什麼是動態規劃五部曲!
大家好,我是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站上關注我,上面有很多演算法的講解影片。
碼字不已,希望對你有所幫助!
@程式碼隨想錄
點個贊就是對我最大的鼓勵,筆芯~