數(shù)據(jù)結(jié)構(gòu)與算法之動態(tài)規(guī)劃就這些招式！
動態(tài)規(guī)劃理論基礎(chǔ)
什么是動態(tài)規(guī)劃
動態(tài)規(guī)劃，英文：Dynamic Programming，簡稱DP，如果某一問題有很多重疊子問題，使用動態(tài)規(guī)劃是最有效的。
所以動態(tài)規(guī)劃中每一個狀態(tài)一定是由上一個狀態(tài)推導(dǎo)出來的，這一點就區(qū)分于貪心，貪心沒有狀態(tài)推導(dǎo)，而是從局部直接選最優(yōu)的，
在關(guān)于貪心算法，你該了解這些!中我舉了一個背包問題的例子。
例如：有N件物品和一個最多能背重量為W 的背包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價值總和最大。
動態(tài)規(guī)劃中dp[j]是由dp[j-weight[i]]推導(dǎo)出來的，然后取max(dp[j], dp[j - weight[i]] + value[i])。
但如果是貪心呢，每次拿物品選一個最大的或者最小的就完事了，和上一個狀態(tài)沒有關(guān)系。
所以貪心解決不了動態(tài)規(guī)劃的問題。
其實大家也不用死扣動規(guī)和貪心的理論區(qū)別，后面做做題目自然就知道了。
而且很多講解動態(tài)規(guī)劃的文章都會講最優(yōu)子結(jié)構(gòu)啊和重疊子問題啊這些，這些東西都是教科書的上定義，晦澀難懂而且不實用。
大家知道動規(guī)是由前一個狀態(tài)推導(dǎo)出來的，而貪心是局部直接選最優(yōu)的，對于刷題來說就夠用了。
上述提到的背包問題，后序會詳細講解。
動態(tài)規(guī)劃的解題步驟
做動規(guī)題目的時候，很多同學會陷入一個誤區(qū)，就是以為把狀態(tài)轉(zhuǎn)移公式背下來，照葫蘆畫瓢改改，就開始寫代碼，甚至把題目AC之后，都不太清楚dp[i]表示的是什么。
這就是一種朦朧的狀態(tài)，然后就把題給過了，遇到稍稍難一點的，可能直接就不會了，然后看題解，然后繼續(xù)照葫蘆畫瓢陷入這種惡性循環(huán)中。
狀態(tài)轉(zhuǎn)移公式(遞推公式)是很重要，但動規(guī)不僅僅只有遞推公式。
對于動態(tài)規(guī)劃問題，我將拆解為如下五步曲，這五步都搞清楚了，才能說把動態(tài)規(guī)劃真的掌握了!
- 確定dp數(shù)組(dp table)以及下標的含義
- 確定遞推公式
- dp數(shù)組如何初始化
- 確定遍歷順序
- 舉例推導(dǎo)dp數(shù)組
一些同學可能想為什么要先確定遞推公式，然后在考慮初始化呢?
因為一些情況是遞推公式?jīng)Q定了dp數(shù)組要如何初始化!
后面的講解中我都是圍繞著這五點來進行講解。
可能刷過動態(tài)規(guī)劃題目的同學可能都知道遞推公式的重要性，感覺確定了遞推公式這道題目就解出來了。
其實 確定遞推公式 僅僅是解題里的一步而已!
一些同學知道遞推公式，但搞不清楚dp數(shù)組應(yīng)該如何初始化，或者正確的遍歷順序，以至于記下來公式，但寫的程序怎么改都通過不了。
后序的講解的大家就會慢慢感受到這五步的重要性了。
動態(tài)規(guī)劃應(yīng)該如何debug
相信動規(guī)的題目，很大部分同學都是這樣做的。
看一下題解，感覺看懂了，然后照葫蘆畫瓢，如果能正好畫對了，萬事大吉，一旦要是沒通過，就怎么改都通過不了，對 dp數(shù)組的初始化，遞推公式，遍歷順序，處于一種黑盒的理解狀態(tài)。
寫動規(guī)題目，代碼出問題很正常!
找問題的最好方式就是把dp數(shù)組打印出來，看看究竟是不是按照自己思路推導(dǎo)的!
一些同學對于dp的學習是黑盒的狀態(tài)，就是不清楚dp數(shù)組的含義，不懂為什么這么初始化，遞推公式背下來了，遍歷順序靠習慣就是這么寫的，然后一鼓作氣寫出代碼，如果代碼能通過萬事大吉，通過不了的話就憑感覺改一改。
這是一個很不好的習慣!
做動規(guī)的題目，寫代碼之前一定要把狀態(tài)轉(zhuǎn)移在dp數(shù)組的上具體情況模擬一遍，心中有數(shù)，確定最后推出的是想要的結(jié)果。
然后再寫代碼，如果代碼沒通過就打印dp數(shù)組，看看是不是和自己預(yù)先推導(dǎo)的哪里不一樣。
如果打印出來和自己預(yù)先模擬推導(dǎo)是一樣的，那么就是自己的遞歸公式、初始化或者遍歷順序有問題了。
如果和自己預(yù)先模擬推導(dǎo)的不一樣，那么就是代碼實現(xiàn)細節(jié)有問題。
這樣才是一個完整的思考過程，而不是一旦代碼出問題，就毫無頭緒的東改改西改改，最后過不了，或者說是稀里糊涂的過了。
這也是我為什么在動規(guī)五步曲里強調(diào)推導(dǎo)dp數(shù)組的重要性。
舉個例子哈：在「代碼隨想錄」刷題小分隊微信群里，一些錄友可能代碼通過不了，會把代碼拋到討論群里問：我這里代碼都已經(jīng)和題解一模一樣了，為什么通過不了呢?
發(fā)出這樣的問題之前，其實可以自己先思考這三個問題：
- 這道題目我舉例推導(dǎo)狀態(tài)轉(zhuǎn)移公式了么?
- 我打印dp數(shù)組的日志了么?
- 打印出來了dp數(shù)組和我想的一樣么?
如果這靈魂三問自己都做到了，基本上這道題目也就解決了，或者更清晰的知道自己究竟是哪一點不明白，是狀態(tài)轉(zhuǎn)移不明白，還是實現(xiàn)代碼不知道該怎么寫，還是不理解遍歷dp數(shù)組的順序。
然后在問問題，目的性就很強了，群里的小伙伴也可以快速知道提問者的疑惑了。
注意這里不是說不讓大家問問題哈， 而是說問問題之前要有自己的思考，問題要問到點子上!
大家工作之后就會發(fā)現(xiàn)，特別是大廠，問問題是一個專業(yè)活，是的，問問題也要體現(xiàn)出專業(yè)!
如果問同事很不專業(yè)的問題，同事們會懶的回答，領(lǐng)導(dǎo)也會認為你缺乏思考能力，這對職場發(fā)展是很不利的。
所以大家在刷題的時候，就鍛煉自己養(yǎng)成專業(yè)提問的好習慣。
總結(jié)
這一篇是動態(tài)規(guī)劃的整體概述，講解了什么是動態(tài)規(guī)劃，動態(tài)規(guī)劃的解題步驟，以及如何debug。
動態(tài)規(guī)劃是一個很大的領(lǐng)域，今天這一篇講解的內(nèi)容是整個動態(tài)規(guī)劃系列中都會使用到的一些理論基礎(chǔ)。
在后序講解中針對某一具體問題，還會講解其對應(yīng)的理論基礎(chǔ)，例如背包問題中的01背包，leetcode上的題目都是01背包的應(yīng)用，而沒有純01背包的問題，那么就需要在把對應(yīng)的理論知識講解一下。
大家會發(fā)現(xiàn)，我講解的理論基礎(chǔ)并不是教科書上各種動態(tài)規(guī)劃的定義，錯綜復(fù)雜的公式。
這里理論基礎(chǔ)篇已經(jīng)是非常偏實用的了，每個知識點都是在解題實戰(zhàn)中非常有用的內(nèi)容，大家要重視起來哈。
