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

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