什么是動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃，英文：Dynamic Programming，簡(jiǎn)稱DP，如果某一問(wèn)題有很多重疊子問(wèn)題，使用動(dòng)態(tài)規(guī)劃是最有效的。

所以動(dòng)態(tài)規(guī)劃中每一個(gè)狀態(tài)一定是由上一個(gè)狀態(tài)推導(dǎo)出來(lái)的，這一點(diǎn)就區(qū)分于貪心，貪心沒(méi)有狀態(tài)推導(dǎo)，而是從局部直接選最優(yōu)的，

在關(guān)于貪心算法，你該了解這些!中我舉了一個(gè)背包問(wèn)題的例子。

例如：有N件物品和一個(gè)最多能背重量為W 的背包。第i件物品的重量是weight[i]，得到的價(jià)值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價(jià)值總和最大。

動(dòng)態(tài)規(guī)劃中dp[j]是由dp[j-weight[i]]推導(dǎo)出來(lái)的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是貪心呢，每次拿物品選一個(gè)最大的或者最小的就完事了，和上一個(gè)狀態(tài)沒(méi)有關(guān)系。

所以貪心解決不了動(dòng)態(tài)規(guī)劃的問(wèn)題。

其實(shí)大家也不用死扣動(dòng)規(guī)和貪心的理論區(qū)別，后面做做題目自然就知道了。

而且很多講解動(dòng)態(tài)規(guī)劃的文章都會(huì)講最優(yōu)子結(jié)構(gòu)啊和重疊子問(wèn)題啊這些，這些東西都是教科書(shū)的上定義，晦澀難懂而且不太實(shí)用。

大家知道動(dòng)規(guī)是由前一個(gè)狀態(tài)推導(dǎo)出來(lái)的，而貪心是局部直接選最優(yōu)的，對(duì)于刷題來(lái)說(shuō)就夠用了。

上述提到的背包問(wèn)題，后序會(huì)詳細(xì)講解。

動(dòng)態(tài)規(guī)劃的解題步驟

做動(dòng)規(guī)題目的時(shí)候，很多同學(xué)會(huì)陷入一個(gè)誤區(qū)，就是以為把狀態(tài)轉(zhuǎn)移公式背下來(lái)，照葫蘆畫(huà)瓢改改，就開(kāi)始寫(xiě)代碼，甚至把題目AC之后，都不太清楚dp[i]表示的是什么。

這就是一種朦朧的狀態(tài)，然后就把題給過(guò)了，遇到稍稍難一點(diǎn)的，可能直接就不會(huì)了，然后看題解，然后繼續(xù)照葫蘆畫(huà)瓢陷入這種惡性循環(huán)中。

狀態(tài)轉(zhuǎn)移公式(遞推公式)是很重要，但動(dòng)規(guī)不僅僅只有遞推公式。

對(duì)于動(dòng)態(tài)規(guī)劃問(wèn)題，我將拆解為如下五步曲，這五步都搞清楚了，才能說(shuō)把動(dòng)態(tài)規(guī)劃真的掌握了!

• 確定dp數(shù)組(dp table)以及下標(biāo)的含義
• 確定遞推公式
• dp數(shù)組如何初始化
• 確定遍歷順序
• 舉例推導(dǎo)dp數(shù)組

一些同學(xué)可能想為什么要先確定遞推公式，然后在考慮初始化呢?

因?yàn)橐恍┣闆r是遞推公式?jīng)Q定了dp數(shù)組要如何初始化!

后面的講解中我都是圍繞著這五點(diǎn)來(lái)進(jìn)行講解。

可能刷過(guò)動(dòng)態(tài)規(guī)劃題目的同學(xué)可能都知道遞推公式的重要性，感覺(jué)確定了遞推公式這道題目就解出來(lái)了。

其實(shí) 確定遞推公式 僅僅是解題里的一步而已!

一些同學(xué)知道遞推公式，但搞不清楚dp數(shù)組應(yīng)該如何初始化，或者正確的遍歷順序，以至于記下來(lái)公式，但寫(xiě)的程序怎么改都通過(guò)不了。

后序的講解的大家就會(huì)慢慢感受到這五步的重要性了。

動(dòng)態(tài)規(guī)劃應(yīng)該如何debug

相信動(dòng)規(guī)的題目，很大部分同學(xué)都是這樣做的。

看一下題解，感覺(jué)看懂了，然后照葫蘆畫(huà)瓢，如果能正好畫(huà)對(duì)了，萬(wàn)事大吉，一旦要是沒(méi)通過(guò)，就怎么改都通過(guò)不了，對(duì) dp數(shù)組的初始化，遞歸公式，遍歷順序，處于一種黑盒的理解狀態(tài)。

寫(xiě)動(dòng)規(guī)題目，代碼出問(wèn)題很正常!

找問(wèn)題的最好方式就是把dp數(shù)組打印出來(lái)，看看究竟是不是按照自己思路推導(dǎo)的!

一些同學(xué)對(duì)于dp的學(xué)習(xí)是黑盒的狀態(tài)，就是不清楚dp數(shù)組的含義，不懂為什么這么初始化，遞推公式背下來(lái)了，遍歷順序靠習(xí)慣就是這么寫(xiě)的，然后一鼓作氣寫(xiě)出代碼，如果代碼能通過(guò)萬(wàn)事大吉，通過(guò)不了的話就憑感覺(jué)改一改。

這是一個(gè)很不好的習(xí)慣!

做動(dòng)規(guī)的題目，寫(xiě)代碼之前一定要把狀態(tài)轉(zhuǎn)移在dp數(shù)組的上具體情況模擬一遍，心中有數(shù)，確定最后推出的是想要的結(jié)果。

然后再寫(xiě)代碼，如果代碼沒(méi)通過(guò)就打印dp數(shù)組，看看是不是和自己預(yù)先推導(dǎo)的哪里不一樣。

如果打印出來(lái)和自己預(yù)先模擬推導(dǎo)是一樣的，那么就是自己的遞歸公式、初始化或者遍歷順序有問(wèn)題了。

如果和自己預(yù)先模擬推導(dǎo)的不一樣，那么就是代碼實(shí)現(xiàn)細(xì)節(jié)有問(wèn)題。

這樣才是一個(gè)完整的思考過(guò)程，而不是一旦代碼出問(wèn)題，就毫無(wú)頭緒的東改改西改改，最后過(guò)不了，或者說(shuō)是稀里糊涂的過(guò)了。

這也是我為什么在動(dòng)規(guī)五步曲里強(qiáng)調(diào)推導(dǎo)dp數(shù)組的重要性。

舉個(gè)例子哈：在「代碼隨想錄」刷題小分隊(duì)微信群里，一些錄友可能代碼通過(guò)不了，會(huì)把代碼拋到討論群里問(wèn)：我這里代碼都已經(jīng)和題解一模一樣了，為什么通過(guò)不了呢?

發(fā)出這樣的問(wèn)題之前，其實(shí)可以自己先思考這三個(gè)問(wèn)題：

• 這道題目我舉例推導(dǎo)狀態(tài)轉(zhuǎn)移公式了么?
• 我打印dp數(shù)組的日志了么?
• 打印出來(lái)了dp數(shù)組和我想的一樣么?

如果這靈魂三問(wèn)自己都做到了，基本上這道題目也就解決了，或者更清晰的知道自己究竟是哪一點(diǎn)不明白，是狀態(tài)轉(zhuǎn)移不明白，還是實(shí)現(xiàn)代碼不知道該怎么寫(xiě)，還是不理解遍歷dp數(shù)組的順序。

然后在問(wèn)問(wèn)題，目的性就很強(qiáng)了，群里的小伙伴也可以快速知道提問(wèn)者的疑惑了。

注意這里不是說(shuō)不讓大家問(wèn)問(wèn)題哈， 而是說(shuō)問(wèn)問(wèn)題之前要有自己的思考，問(wèn)題要問(wèn)到點(diǎn)子上!

大家工作之后就會(huì)發(fā)現(xiàn)，特別是大廠，問(wèn)問(wèn)題是一個(gè)專業(yè)活，是的，問(wèn)問(wèn)題也要體現(xiàn)出專業(yè)!

如果問(wèn)同事很不專業(yè)的問(wèn)題，同事們會(huì)懶的回答，領(lǐng)導(dǎo)也會(huì)認(rèn)為你缺乏思考能力，這對(duì)職場(chǎng)發(fā)展是很不利的。

所以大家在刷題的時(shí)候，就鍛煉自己，養(yǎng)成專業(yè)提問(wèn)的好習(xí)慣。

總結(jié)

這一篇是動(dòng)態(tài)規(guī)劃的整體概述，講解了什么是動(dòng)態(tài)規(guī)劃，動(dòng)態(tài)規(guī)劃的解題步驟，以及如何debug。

動(dòng)態(tài)規(guī)劃是一個(gè)很大的領(lǐng)域，今天這一篇講解的內(nèi)容是整個(gè)動(dòng)態(tài)規(guī)劃系列中都會(huì)使用到的一些理論基礎(chǔ)。

在后序講解中針對(duì)某一具體問(wèn)題，還會(huì)講解其對(duì)應(yīng)的理論基礎(chǔ)，例如背包問(wèn)題中的01背包，leetcode上的題目都是01背包的應(yīng)用，而沒(méi)有純01背包的問(wèn)題，那么就需要在把對(duì)應(yīng)的理論知識(shí)講解一下。

大家會(huì)發(fā)現(xiàn)，我講解的理論基礎(chǔ)并不是教科書(shū)上各種動(dòng)態(tài)規(guī)劃的定義，錯(cuò)綜復(fù)雜的公式。

這里理論基礎(chǔ)篇已經(jīng)是非常偏實(shí)用的了，每個(gè)知識(shí)點(diǎn)都是在解題實(shí)戰(zhàn)中非常有用的內(nèi)容，大家要重視起來(lái)哈。

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。