入職大廠？程式設計師繞不開的核心演算法之動態規劃

Q1 什麼是動態規劃

動態規劃既是數學最佳化方法又是計算機程式設計方法。該方法是由理查德·貝爾曼（Richard Bellman）在1950年代開發的，並且已在從航空航天工程到經濟學的許多領域中得到應用。在這兩種情況下，它都是指透過以遞迴的方式將其分解為更簡單的問題來簡化複雜的問題。雖然無法以這種方式解決某些決策問題，但跨越多個時間點的決策通常會遞迴拆分。同樣，在計算機科學中，如果可以透過將問題分解為子問題然後遞迴地找到子問題的最優解來最佳地解決問題，則可以說它具有最優結構。如果子問題可以遞迴巢狀在較大的問題內，從而可以應用動態程式設計方法，則較大問題的值與子問題的值之間存在關係。

Q2 動態規劃問題特徵

最優子結構：子問題最優決策可匯出原問題最優決策無後效性

重疊子問題：去冗餘空間換時間

1，最優子結構：透過子問題的最優解，推導問題最優解

2，無後效性：只關心前一個狀態，不關心推導過程

3，重複問題：不同的決策階段有重複的狀態

Q3 最優問題

求A->B的最短路f（B），等價於求B的前驅x的最短路，加上一條x->B的邊。

因為要到B，必須經過B的某個前驅x，而我們又不知道要經過哪個x——列舉x

我們選擇所有f（x） + w（x->B） 最小的點作為f（B）

子問題

A->x，對於所有x都要解才行

“貪心”，選取總和最小的

Q4 自動機模型

我們有狀態集，有初始狀態S，有終結狀態（集合）T。有評價函式f， 有狀態轉化規則和cost，revenve函式，我們求從S，轉化到T狀態的最小代價（最大收益）。

無後效性

從S到達狀態T的最小代價是一定的，而和到達狀態T的具體方式無關。即最小代價只和狀態有關。

Q5動態規劃的解題思路

1.將原問題分解為子問題

子問題和原問題形式相同或類似。子問題解決了，原問題即解決

2.定義陣列元素的含義

用一個一維或兩維陣列，來儲存歷史記錄，子問題的解一旦求出就儲存到陣列中，“陣列”的大小與用動態規劃的時間複雜度直接相關

3.找出陣列元素之間的關係式

找出如何利用歷史資料來推出新的元素值，也就是找到陣列元素之間的關係式，例如 dp［n］ = dp［n-1］ + dp［n-2］

4.確定一些初始值

初始化，例如dp［2］ 和 dp［1］ 是不能再分解的了，所以必須要找到直接獲得 dp［2］ 和 dp［1］ 的值

Q6 動態規劃的基本步驟

• 設計暴力演算法，找到冗餘

• 設計並存儲狀態（一維，二維，三維陣列）

• 遞迴式（狀態轉移方程）

• 自底向上計算最優解（程式設計方式）

Q7 TSP問題

給定一個有權圖，可以理解為完全圖，每條邊的邊權稱為代價，找到一個代價最小的圈包含所有節點。

解法一：暴力列舉，因為是圈所以共有（n-1）！種情況，列舉所有的圈然後遞迴，dfs

剪枝：如果當前列舉的總權值已經不小於已經搜到的最優解就放棄這個解。

解法二：首先思考需要是否要考慮各節點間的順序比如ABCD和ACBD什麼區別。兩者都是從A節點開始，都是停留在D點。這裡我們只需要保留權值和較小的就可以了，

然後定義狀態，經歷了哪些點（z的n次方-點陣圖），停留在哪些點（直接記錄標號）。可以定義為（passed，end）這樣的對。

列舉狀態：從end出發走到下一個節點x，這個點不能再passed出現即passed第x個bit是0從而end’=x。passed’=passed把第x位改成1（位運算passed’=passed|（1<

定義變數dp［passed］［end］表示經過passed表示的這些點停留在end時的最優值

dp［passed’］［x］=min{所以可以轉化成該狀態的其他狀態（passed，end）+weight（end，x）}

必須列舉所有狀態才能找到最優值（狀態個數n乘2的n次方還是指數級的）

普通思維的定式是列舉所有的解O（（n-1）！），這也是一種狀態表示（笨方法）

一個狀態下有多個解 （如ABCD，ACBD）我們只選擇了最優的，實質是剪枝

為什麼這樣定義狀態？

如果兩個（部分）解屬於同一個狀態，從這裡開始它們可以選擇的點是一樣的——狀態是解的“等價類”

Q8 找零錢問題

用面值為A1、A2。。。。An的錢幣，每種無限多，湊一定數量的錢B，使用錢幣數量最少

解法一：暴力列舉

解法二：假設我們使用了一個Ai（1<=i<=n），則B-Ai一定也要最優。問題在於我們不知道Ai是否被使用，可以用列舉

狀態表示，一定錢數下，最小的錢幣個數為dp［X］

dp［X］=infinity for x<0

dp［0］=0

dp［X］=min{f（x-Ai）+1} X>0，i=1，2，3。。。n

Q9 常見的狀態表示

一維

找零錢 f（x） = f（x’） +… （LIS）

斐波那契數列 f（x） = f（x – 1） + f（x – 2）

臺階 f（x） = f（x – 1） + f（x – 2） + f（x – 3）

高維 （序列問題）

［i］［j］，第一個串前i位和第二個串前j位的最優值（LCS，edit-distance）， 揹包

序列［i。。j］的最優值，拆成［i。。k］ + ［k + 1。。j］ + merge（left，right） 像分治

記錄任何你需要的東西：格子取數問題

要記錄中間經過的點——引入集合 2的n次方

TSP問題

樹型：最優二叉搜尋樹

10 總結

想要的回答：之前在xx地方吃了xx餐廳，覺得很好吃，就希望一家店，讓杭州人…

貪心演算法

比較直觀，容易想到

對“圖”要求高

很多特殊圖上的問題可以

證明比較困難

有時需要先排序，再貪心

動態規劃

不是純粹的列舉，是“聰明的”列舉，我們列舉的一個狀態通常對應“很 多”種可能。

貪心是特殊的動態規劃 （子問題不重疊）

狀態轉移方程

實質是狀態圖邊的表示，尋找狀態x的所有前驅y其實是一條邊兩個端點之間的關係。