1、第 PAGE6 頁 共 NUMPAGES6 頁干貨動態(tài)規(guī)劃十問十答 【干貨】動態(tài)規(guī)劃十問十答 問 問 1 ：動態(tài)規(guī)劃是個什么鳥蛋？答：動態(tài)規(guī)劃是一種通過“大而化小”的思路解決問題的算法。區(qū)別于一些固定形式的算法，如二分法，寬度優(yōu)先搜索法，動態(tài)規(guī)劃沒有實際的步驟來規(guī)定第一步做什么第二步做什么。所以更加確切的說，動態(tài)規(guī)劃是一種解決問題的思想。這種思想的本質(zhì)是，一個規(guī)模比擬大的問題假設(shè)用 2-3 個參數(shù)可以表示，是通過規(guī)模比擬小的假設(shè)干問題的結(jié)果來得到的通過取最大，取最小，或者加起來之類的運算所以我們經(jīng)常看到的動態(tài)規(guī)劃的核心-狀態(tài)轉(zhuǎn)移方程都長成這樣：j = fi - 1j + fij - 1 = m

2、a_f if j B 有 2 條途徑，一條代價為 10，另外一條代價為 100，B-終點有 1024 條途徑。當(dāng)我們選擇了代價為 10 的那條途徑走到 B 時，可以繼續(xù)往下走完 1024 條途徑到終點，但是在此之后，我們再從代價為100 的途徑從 A 走到 B 時，我們可以發(fā)現(xiàn)此時無論如何走，都不可能有剛剛從 10的途徑走過來更好，所以這些計算是“無用”的計算，也可以說是“重復(fù)”的計算。這就是動態(tài)規(guī)劃之所以“快”的重要原因。問 問 4 ：學(xué)習(xí)動態(tài)規(guī)劃有什么捷徑？答：我們將動態(tài)規(guī)劃的常見類型分為如下幾種：矩陣 序列型 雙序列型 劃分 區(qū)間 背包型 狀態(tài)壓縮型 _樹型其中，在技術(shù)面試中經(jīng)常出現(xiàn)的是

3、矩陣型，序列型和雙序列型。劃分型，區(qū)間型和背包型偶然出現(xiàn)。狀態(tài)壓縮和樹型根本不會出現(xiàn)一般在算法競賽中才會出現(xiàn)。每種類型都有著自己的題目特點和狀態(tài)的表示方法。以矩陣型動態(tài)規(guī)劃為例，一般題目會給你一個矩陣，告訴你有一個小人在上面走動，每次只能向右和向下走，然后問你比方有多少種方案從左上走到右下 (problem/unique-paths/)。這種類型狀態(tài)表示的特點一般是使用坐標(biāo)作為狀態(tài)，如 fij表示走到(i,j)這個位置的時候，一共有多少種方案。狀態(tài)的轉(zhuǎn)移那么是考慮是從哪兒走到(i,j)這個坐標(biāo)的。而序列型的動態(tài)規(guī)劃，一般是告訴你一個序列；雙序列的動態(tài)規(guī)劃一般是告訴你兩個字符串或者兩個序列。將所

4、做過的動態(tài)規(guī)劃問題按照這些類別進(jìn)展歸類，分析p 狀態(tài)的表示方法和狀態(tài)轉(zhuǎn)移方程的構(gòu)造方法在每種類型中的近似之處，會讓你更快的學(xué)會動態(tài)規(guī)劃。問 問 5 ：什么樣的問題合適使用動態(tài)規(guī)劃？答：可以使用動態(tài)規(guī)劃的問題一般都有一些特點可以遵循。如題目的問法一般是三種方式：1最大值/最小值 2.求可不可行 假如你碰到一個問題，是問你這三個問題之一的，那么有 90%的概率是使用動態(tài)規(guī)劃來求解。要重點說明的是，假如一個問題讓你求出“所有的”方案和結(jié)果，那么肯定不是使用動態(tài)規(guī)劃。問 問 6 ：解決一個動態(tài)規(guī)劃問題的步驟是什么？答：首先根據(jù)“問 5”判斷是否是動態(tài)規(guī)劃的問題，假如是，那么嘗試將其按照“問 4”進(jìn)展分

5、類，找到對應(yīng)的類別和相似的問題。接著從下面的 4 個要素去逐步剖析解決這道題：每個步驟分析p 完成之后，就根本上解決了整道動態(tài)規(guī)劃的問題。問 問 7 ：怎樣優(yōu)化動態(tài)規(guī)劃的時間？答：一般來說，使用動態(tài)規(guī)劃求解的問題，時間上已經(jīng)比暴力搜索要優(yōu)化很多了。但是仍然存在著一些可以優(yōu)化的空間。通常來說，動態(tài)規(guī)劃的時間優(yōu)化，有如下兩種常見的方式：對于通過變換狀態(tài)來優(yōu)化的問題比擬難，需要一些經(jīng)歷和靈感。而對于決策單調(diào)的優(yōu)化，那么比擬簡單，但適用范圍不廣，一般只適用于劃分型動態(tài)規(guī)劃當(dāng)中，通常這個方法可以將復(fù)雜度降低一個數(shù)量級。問 問 8 ：怎樣優(yōu)化動態(tài)規(guī)劃的空間？答：動態(tài)規(guī)劃的空間優(yōu)化只有一種方法，就是使用滾動

6、數(shù)組進(jìn)展優(yōu)化。以一個二維的動態(tài)規(guī)劃為例子。假設(shè)狀態(tài)轉(zhuǎn)移方程如下：fij = fi - 1j + fij - 1。我們可以發(fā)現(xiàn)，第 i 層的狀態(tài)，已經(jīng)和第 i-2 層的狀態(tài)沒有關(guān)系了，那么這種情況下，用于存儲第 i-2 層的空間就可以被重復(fù)利用。方法非常簡單，把數(shù)組的第一維對 2 取模就可以了：fi % 2j = f(i - 1) % 2j + fi % 2j-1。這種方法通常可以將空間復(fù)雜度降低一個數(shù)量級。問 問 9 ：有什么動態(tài)規(guī)劃的書籍和參考資料可以推薦么？yuanbin 的 gitbook：dynamic_programming/inde_ 著名的背包九講：love-oriented./pack/ s/tanGyi7qM8TVE 也可以直接在網(wǎng)上搜索背包九講問 問 10 ：有哪些動態(tài)規(guī)劃題目必需要練習(xí)的？在 LintCode 上包含了 30 余道動態(tài)規(guī)劃的練習(xí)題，都是從實際的面試問題中匯總的精選練習(xí)：tag/dynamic-programming/想要更加扎實的學(xué)習(xí)動態(tài)規(guī)劃算法么？ 本文作者主講的九章算法班熾熱報名中！北京時間 7.19 周日早 9:30-11:30( 美西時間 7.18 周六晚