導(dǎo)讀動(dòng)態(tài)問(wèn)題紛繁復(fù)雜如何系統(tǒng)學(xué)習(xí)和掌握它

其實(shí)，幾乎所有人在初學(xué)算法和動(dòng)態(tài)規(guī)劃時(shí)都會(huì)有這種感受，特別是當(dāng)待解決的問(wèn)題步入“窮舉”這個(gè)不得了的領(lǐng)域時(shí)。窮舉從來(lái)都不是一個(gè)好的解決方案，因此針對(duì)這類(lèi)問(wèn)題的求解方法真是八仙過(guò)海、各顯神通，我們很難直接從這些解法中找到規(guī)律，同時(shí)這些解法又晦澀難懂。但告訴你的是，數(shù)據(jù)結(jié)構(gòu)和算法雖然從表面上看紛繁復(fù)雜，但常用的基本思想和方法還真的就不多。這同樣適用于動(dòng)態(tài)規(guī)劃問(wèn)題，它簡(jiǎn)直就是模板、套路屆的典范。因此，只要我們掌握了正確的學(xué)習(xí)方法，形成經(jīng)驗(yàn)式總結(jié)，那么當(dāng)我們?cè)偃ッ鎸?duì)看似“玄幻”的動(dòng)態(tài)規(guī)劃問(wèn)題時(shí)，就再也不是什么難事了。所以說(shuō)，動(dòng)態(tài)規(guī)劃作為算法面試問(wèn)題中的一項(xiàng)重要議題，從表面上看似紛繁復(fù)雜，但有規(guī)可循。今天，我會(huì)把自己這些年來(lái)總結(jié)的學(xué)習(xí)竅門(mén)、遇到的問(wèn)題和解題思路，進(jìn)行歸納總結(jié)，梳理出一條清晰的路徑給你，即如何系統(tǒng)學(xué)習(xí)和掌握動(dòng)態(tài)規(guī)劃。我期待這個(gè)專(zhuān)欄能讓你產(chǎn)生全新的認(rèn)識(shí)，收獲清晰的解題思路，輕松跨過(guò)大廠算法面試這道坎。建立扎實(shí)的基礎(chǔ)知識(shí)首先，強(qiáng)調(diào)的是，先掌握基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和算法，再來(lái)談動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃不僅名字聽(tīng)起來(lái)十分高級(jí)，它也的確是一種高級(jí)的解決問(wèn)題的思想。為了更好地理解這個(gè)思想，掌握基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)就顯得尤為重要了，比如高維數(shù)組這樣的數(shù)據(jù)結(jié)構(gòu)，就經(jīng)常出現(xiàn)在動(dòng)態(tài)規(guī)劃解法當(dāng)中。其次是算法，像是遞歸、搜索和迭代這些常見(jiàn)的算法，都會(huì)作為工具在動(dòng)態(tài)規(guī)劃解法中使用。這里我再次拿出了開(kāi)篇詞中那張“基石”的。沒(méi)錯(cuò)，你完全可以這樣理解：掌握基礎(chǔ)接著，還有一個(gè)值得強(qiáng)調(diào)的問(wèn)題，就是鍛煉算法編碼能力，請(qǐng)不要忽視實(shí)踐的力量。我曾不止一次在面試環(huán)節(jié)中，看到面試者在白板上糾結(jié)于這樣的問(wèn)題：我是否該在循環(huán)上加上等號(hào)這個(gè)條件？加等號(hào)1for(inti=0;i<=MAX_COUNT;i++){...還是不加等號(hào)1for(inti=0;i<MAX_COUNT;i++){...還是換個(gè)方法1for(inti=0;i<MAX_COUNT+1;i++){...不知道你看到這里，是否會(huì)心一笑？是的，在面試過(guò)程中，白板是沒(méi)辦法拿給我們做現(xiàn)場(chǎng)調(diào)試的。因此，能否快速地寫(xiě)出干凈漂亮的代碼，不僅能讓自己的思路愈發(fā)清晰，還能盡量避免錯(cuò)誤。正所謂細(xì)節(jié)是，在平時(shí)學(xué)習(xí)、練習(xí)的過(guò)程中，你要重視細(xì)節(jié)、重視細(xì)節(jié)、重視細(xì)節(jié)，透徹理解動(dòng)態(tài)規(guī)劃的基本方我剛才有提到，動(dòng)態(tài)規(guī)劃是一種思想，是一種高級(jí)方法。我們說(shuō)算法是一種簡(jiǎn)單的經(jīng)驗(yàn)總結(jié)和套路。那什么是思想呢？相較于算法，思想的是指導(dǎo)你我來(lái)解決問(wèn)題的。既然是找子問(wèn)題、遞歸求解、子問(wèn)題與無(wú)后效性、狀態(tài)。如果你完全沒(méi)有接觸過(guò)動(dòng)態(tài)規(guī)劃，你可能會(huì)覺(jué)得這幾個(gè)詞已經(jīng)夠頭疼了，但其實(shí)它們都很簡(jiǎn)單，在接下來(lái)的課程里，我會(huì)帶著你弄清楚這里的每一個(gè)概念，同時(shí)也要讓它們落到實(shí)處，看在一個(gè)具體動(dòng)歸問(wèn)題下它們是如何發(fā)揮作用的。那么在理解這些概念及其背后的深意之后，我們需要對(duì)其進(jìn)行歸納總結(jié)。這么做的主要目的在于，你可以擁有一個(gè)清晰的判斷標(biāo)準(zhǔn)：哪些問(wèn)題應(yīng)該使用動(dòng)態(tài)規(guī)劃來(lái)解，而哪些不應(yīng)該或不能使用動(dòng)態(tài)規(guī)劃來(lái)解。避免盲目地使用動(dòng)態(tài)規(guī)劃來(lái)解題，弄清楚這個(gè)問(wèn)題后，我們才能有的放矢地解決算法難題。因此，你完全不需要擔(dān)心，我們的“車(chē)”很穩(wěn)，且車(chē)速適中掌握經(jīng)典問(wèn)題，總結(jié)在你掌握了諸如背包問(wèn)題、子序列問(wèn)題或子數(shù)組問(wèn)題之后，你就會(huì)發(fā)現(xiàn)這些問(wèn)題都可以進(jìn)行歸納總結(jié)。當(dāng)然了，作為專(zhuān)欄，我會(huì)給出詳細(xì)的經(jīng)驗(yàn)總結(jié)，并在后續(xù)課程中的恰當(dāng)時(shí)機(jī)給出嚴(yán)格的推導(dǎo)。這些經(jīng)驗(yàn)總結(jié)在90%以上的情況下都是有效的，易于理解，而且十分適合用來(lái)應(yīng)對(duì)面試。所以，我希望你也能在接下來(lái)的學(xué)習(xí)過(guò)程中，建立自己的經(jīng)驗(yàn)總結(jié)，這些總結(jié)可以是基于這個(gè)專(zhuān)欄的經(jīng)驗(yàn)總結(jié)之上的，也可以是你在學(xué)習(xí)的過(guò)程中發(fā)現(xiàn)的。既然我們主要想解決的問(wèn)題是面試，那么在學(xué)習(xí)過(guò)程中輔以刷題就十分重要了。首先，在專(zhuān)欄中提到的算法問(wèn)題，你都應(yīng)該上手自己去實(shí)現(xiàn)一遍，這樣比單純的讀效果要好上很多！其次，刷題也要講究一個(gè)度，我當(dāng)然希望你能夠輕松應(yīng)對(duì)國(guó)內(nèi)大廠或國(guó)際大廠的算法面試環(huán)節(jié)，但是你還是應(yīng)該循序漸進(jìn)，慢慢提升刷題數(shù)量和刷題的題目難度。正所謂欲速則不達(dá)！及時(shí)總結(jié)，舉動(dòng)態(tài)規(guī)劃的思想是從一系列算法中演進(jìn)而來(lái)的。貪心算法是求解整體最優(yōu)的真正思路源頭，我們從那里開(kāi)始，考慮窮舉的問(wèn)題，最終通過(guò)優(yōu)化形成了一個(gè)比較完美的總結(jié)。而這個(gè)總結(jié)，正是動(dòng)態(tài)規(guī)劃思想。所以你看，即便是高級(jí)如動(dòng)態(tài)規(guī)劃這樣的思想，也是通過(guò)不斷的總結(jié)而得到的。而經(jīng)過(guò)我們前面這一系列的總結(jié)，便形成了下面這幅腦圖，你可以通過(guò)這幅圖對(duì)學(xué)習(xí)動(dòng)態(tài)規(guī)劃有一個(gè)全面的了解。我有一個(gè)習(xí)慣，就是在刷題之后會(huì)把關(guān)鍵信息做一個(gè)總結(jié)，然后到刷題上。隨著時(shí)間的推移，有些會(huì)點(diǎn)贊。雖然只是一個(gè)不起眼的點(diǎn)贊，但真落到你身上時(shí)，它還是會(huì)成為一個(gè)積極的推動(dòng)力，會(huì)莫名地鼓勵(lì)你在以后的刷題過(guò)程中繼續(xù)觀點(diǎn)。就算觀點(diǎn)不對(duì)，有