截圖摘自湖南大學彭鵬老師的ppt。筆記也是根據(jù)他的ppt整理的。

動態(tài)規(guī)劃

核心

用數(shù)組記錄中間結(jié)果，避免重復(fù)計算

三角數(shù)塔問題

問題描述

給定一個三角形數(shù)塔，從頂部出發(fā)，每次只能移動到下一行的相鄰元素。要求找到一條路徑，使得路徑上的數(shù)字和最大。

假設(shè)有一個三角形數(shù)塔，如下所示：

    37 42 4 68 5 9 3

dp數(shù)組 dp[i][j]表示以matrix[i][j]為結(jié)尾的，最大路徑的和

    310 712 14 1320 19 23 16

最后結(jié)果是23

解題思路

dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+matrix[i][j];

偽代碼

int max_value(vector<vector<int>> &matrix ){vector<vector<int>> dp(matrix.size(),vector<int>(matrix.size()));dp[0][0] = matrix[0][0];for(int i=1;i<matrix.size();i++){dp[i][0] = dp[i-1][0] + matrix[i][0]; // 最左邊的for(int j=1;j<i;j++){// 中間的dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + matrix[i][j];}// 最右邊的dp[i][i] = dp[i-1][i-1] + matrix[i][i];}return max(dp.back().begin(),dp.back().end());    
};

復(fù)雜度分析

時間復(fù)雜度：O(n^2)，其中 n 是三角形的行數(shù)。
空間復(fù)雜度：O(n^2)，其中 n 是三角形的行數(shù)。

最大字段和

問題描述

給定由n個整數(shù)（可能有負整數(shù)）組成的序列(a1, a2, …, an)，最大子段和問題要求該序列形如 的最大值（1≤i≤j≤n），當序列中所有整數(shù)均為負整數(shù)時，其最大子段和為0。

示例

例如，序列(-20,11,-4,13, -5, -2)的最大子段和為 a2+a3+a4=20 。

dp[i]表示以a[i]開頭的，從a[i]–>a.back()的最大子段和

dp數(shù)組

dp[i] = max(dp[i+1]+a[i],a[i]);

	1	2	3	4	5	6
a	-20	11	-4	13	-5	-2
dp	0	20	9	13	-5	-2

所以最后答案是20

// 注意是后序
int max_sub_array(vector<int> &a){int n = a.size();vector<int> dp(n);dp.back() = a.back();int max_sum = a[0];for(int i=n-2;i>=0;i--){dp[i] = max(dp[i+1]+a[i],a[i]);max_sum = max(max_sum,dp[i]);}return max_sum;
}

復(fù)雜度分析

時間復(fù)雜度：O(n)，其中 n 是序列的長度。
空間復(fù)雜度：O(n)，其中 n 是序列的長度。

最長公共子序列

問題描述

給定兩個字符串str1和str2，返回兩個字符串的最長公共子序列（LCS）。

子序列是指從原字符串中刪除若干個字符后，不改變剩余字符順序得到的字符串。最長公共子序列是兩個字符串所共同擁有的最長子序列。

例如，對于字符串"abcde"和"ace"，最長公共子序列是"ace"，因此長度為3。

示例

abcbdab
bdcaba

dp[i][j]表示str1[0:i]和str2[0:j]的最長公共子序列長度

	start	a	b	c	b	d	a	b
start	0	0	0	0	0	0	0	0
b	0	0	1	1	1	1	1	1
d	0	0	1	1	1	2	2	2
c	0	0	1	2	2	2	2	2
a	0	1	1	2	2	2	3	3
b	0	1	2	2	3	3	3	4
a	0	1	2	2	3	3	4	4

所以最后答案是4 bdab

代碼

int longest_common_subsequence(string &str1,string &str2){int n = str1.size();int m = str2.size();vector<vector<int>> dp(n+1,vector<int>(m+1,0));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(str1[i-1] == str2[j-1]){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}}}return dp[n][m];
}

復(fù)雜度分析

時間復(fù)雜度：O(nm)，其中 n 和 m 分別是字符串 str1 和 str2 的長度。
空間復(fù)雜度：O(nm)，其中 n 和 m 分別是字符串 str1 和 str2 的長度。

01背包問題

問題描述

給定 n 種物品和一個容量為 w 的背包，每種物品都只有一件可用。第 i 種物品的體積是 vi，價值是 wi。求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。輸出最大價值。

示例

number=4 capacity=8

i	1	2	3	4
s (weight)	2	3	4	5
v (value)	3	4	5	6

dp數(shù)組

dp[i][j]表示，在總?cè)萘繛閖的情況下，在0~i個物品中，能獲得的最大價值。

dp[i][j]=max(dp[i-1][j],dp[i-1][j-s[i]]+v[i])

	0	1	2	3	4	5	6	7	8
1	0	0	3	3	3	3	3	3	3
2	0	0	3	4	4	7	7	7	7
3	0	0	3	4	4	7	8	9	9
4	0	0	3	4	4	7	8	9	10

代碼

int max_value_in_knapsack(vector<int> &s,vector<int> &v,int capacity){int n = s.size();vector<vector<int>> dp(n+1,vector<int>(capacity+1,0));for(int i=1;i<=n;i++){for(int j=1;j<=capacity;j++){if(j>=s[i-1]){dp[i][j] = max(dp[i-1][j],dp[i-1][j-s[i-1]]+v[i-1]);}else{dp[i][j] = dp[i-1][j];}}}return dp[n][capacity];
}

復(fù)雜度分析

時間復(fù)雜度：O(nm)，其中 n 和 m 分別是物品的數(shù)量和背包容積。
空間復(fù)雜度：O(nm)，其中 n 和 m 分別是物品的數(shù)量和背包容積。

貪心算法

選取局部最優(yōu)解

優(yōu)缺點

• 優(yōu)點：速度快，復(fù)雜度低
• 缺點：需要證明是最優(yōu)解

活動選擇問題

問題描述

假設(shè)我們存在這樣一個活動集合S={a1,a2,a3,a4,…,an},其中每一個活動ai都有一個開始時間si和結(jié)束時間fi保證(0≤si<fi),活動ai進行時，那么它占用的時間為[si,fi)，現(xiàn)在這些活動占用一個共同的資源(教室)，就是這些活動會在某一時間段里面進行安排，如果兩個活動ai和aj的占用時間[si,fi),[sj,fj)不重疊，那么就說明這兩個活動是兼容的，也就是說當sj>=fi或者si>=fj那么活動ai,aj是兼容的。在活動選擇問題中，我們希望選出一個最大兼容活動集，即在同一間教室能安排數(shù)量最多的活動。

貪心策略

按照結(jié)束時間前的，放前面；結(jié)束時間一樣的，開始時間小的放前面，然后依次相加

貪心證明

貪心的結(jié)果集是S, 剩下的集合是T，對于T中的任意一個元素b，都存在一個a屬于S, 是a的結(jié)束時間大于b的開始時間。

代碼

static bool cmp (const vector<int>&a, const vector<int>&b){return a[1]<b[1];}
int eraseOverlapIntervals(vector<vector<int>>& vct) {sort(vct.begin(),vct.end(),cmp);int endtime=vct.front()[1];int res=1;for(int i=1;i<vct.size();i++){if(endtime > vct[i][0]){}else{endtime=vct[i][1];res++;}}return res;}

建議

碰到這種問題，用動態(tài)規(guī)劃也能做，而且如果對應(yīng)的活動有權(quán)值，動態(tài)規(guī)劃還一定是正確的。

1. 對任務(wù)按照結(jié)束時間排序
2. dp[i][j] i表示從0~i個任務(wù)，j表示空余時間，dp[i][j]表示最大解

哈夫曼編碼

問題描述

給定一個由n個不同字符組成的字符串，請設(shè)計一個哈夫曼編碼，使得使用該編碼的編碼長度最小。

哈夫曼樹

• 定義：給定n個權(quán)值作為n個葉子結(jié)點的權(quán)值，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。

解法

• 統(tǒng)計待編碼字符串中每個字符出現(xiàn)的次數(shù)，并將這些次數(shù)作為權(quán)重存儲在數(shù)組中。
• 根據(jù)權(quán)重構(gòu)建哈夫曼樹。在構(gòu)建過程中，每次從權(quán)重數(shù)組中取出兩個最小的權(quán)重，將它們合并為一個新節(jié)點，新節(jié)點的權(quán)重為這兩個節(jié)點權(quán)重之和。然后將新節(jié)點加入哈夫曼樹，同時從權(quán)重數(shù)組中刪除這兩個節(jié)點。重復(fù)這個過程，直到權(quán)重數(shù)組為空。
• 根據(jù)哈夫曼樹生成哈夫曼編碼。對于哈夫曼樹的每個葉子節(jié)點，從根節(jié)點到葉子節(jié)點的路徑上的每個節(jié)點對應(yīng)一個0或1，將這些0和1按照從根節(jié)點到葉子節(jié)點的順序連接起來，就得到了該葉子節(jié)點的哈夫曼編碼。
• 使用哈夫曼編碼對字符串進行編碼。將字符串中的每個字符替換為其哈夫曼編碼，然后將編碼后的字符串按照哈夫曼編碼的規(guī)則進行傳輸或存儲。

最小延遲調(diào)度問題

問題描述

任務(wù)集合S，?i∈S，di 為截止時間，ti為加工時間，di , ti為正整數(shù)。一個調(diào)度f : S→N，f(i)為任務(wù)i 的開始時間。求最大延遲達到最小的調(diào)度，就是所有任務(wù)超過截止時間的和最小。

解決方案

按照結(jié)束時間di從小到大排序，安排時不留空余時間

貪心證明

最優(yōu)解中可以不存在相鄰的逆序任務(wù)，使得（i,j）: f(i) < f(j) di > dj。 （真確解中，交換兩個任意的任務(wù)，都會使得總?cè)蝿?wù)拖延時間變長）。

找零問題

問題描述

考慮用最少的硬幣找n美分零錢的問題。假設(shè)每種硬幣的面額都是整數(shù)。設(shè)計貪心算法求解找零問題，假定有25美分、10美分、5美分和1美分4種面額的硬幣。證明你的算法能找到最優(yōu)解。

解決方案

按照先盡可能用25美分，然后盡可能用10美分，再盡可能用5美分，最后盡可能用1美分。

貪心證明

假設(shè)一個可能的解中，存在兩個10，一個5，則可以用25代替，獲取到一個更優(yōu)解。同樣遞歸，直到?jīng)]有硬幣組合能到25，對應(yīng)著先用25美分的。

圖基本算法

廣度優(yōu)先搜索

算法步驟

廣度優(yōu)先搜索（BFS,Breadth First Search），從初始點開始，逐層向前搜索，即第n層搜索未完成，不得進入下一層搜索。

深度優(yōu)先搜索

算法步驟

深度優(yōu)先搜索（DFS,Depth First Search），從初始點開始，對每一個可能的分支路徑深入到不能再深入為止，而且每個節(jié)點只能訪問一次

歐拉回路

判定條件

對于圖上的任意節(jié)點，入度等于出度。

DFS解法

• 從任意一個起始點v開始DFS遍歷，直到再次到達點v，即尋找一個回路。
• 將此回路定義為C，如果回路C中存在某個點x，其有出邊不在回路中，則繼續(xù)以此點x開始遍歷尋找回路C’，將環(huán)C、C’連接起來也是一個大回路，如此往復(fù)，直到圖G中所有的邊均已經(jīng)添加到回路中
• 顯然每條邊只會返回一次，所以復(fù)雜度為O(E)

用人話說就是：

1. 對任意一個節(jié)點A做DFS, 直到終點到了A，對遍歷的邊進行標記，把所有遍歷的邊去除。
2. 對任意一個還有邊的點B進行DFS，重復(fù)操作，直到所有邊都被標記。
3. 標記的邊就是歐拉回路。

拓撲排序

算法步驟

1. 找到所有入度為0的節(jié)點，并加入隊列
2. 依次從隊列中取出節(jié)點，并將其指向的節(jié)點的入度減1，如果減1后，該節(jié)點的入度為0，則將其加入隊列

最小生成樹

把所有點都連接起來，使得生成樹各邊權(quán)值之和最小。

prim算法

算法步驟

1. 選擇一個節(jié)點作為起始點，并將其加入生成樹中。
2. 選擇與生成樹相連的，最小的邊，將其加入生成樹中。
3. 重復(fù)步驟2，直到所有節(jié)點都被加入生成樹中。
   

復(fù)雜度

• 使用鄰接矩陣表示圖： O(V^2) V是頂點數(shù)量，每次都要找最小的頂點
• 使用鄰接表表示圖： O(ElogV) E是邊的數(shù)量，每次都要找最小的頂點
  （加入新節(jié)點的時候，把新節(jié)點所有相鄰的，不在生成樹中的邊添加進去）

Kruskal算法

算法步驟

1. 按照邊的權(quán)值從小到大排序
2. 依次選擇邊，如果選擇后不會形成環(huán)，則加入生成樹中（使用并查集判斷新加入的邊是否會形成環(huán)）

瓶頸生成樹

定義

一個無向圖G上的瓶頸生成樹是G上一種特殊的生成樹。一個瓶頸生成樹T上權(quán)重最大邊的權(quán)重是G中所有生成樹中最小的。T上最大權(quán)重的邊的權(quán)重稱為T的值。 就是生成樹T，的最大權(quán)值，是G中所有生成樹中，最大權(quán)值的最小值。

單源最短路徑

松弛算法

說人話就是，對于點u --> v , 如果找到另外一個點x，使得u --> x --> v的路徑更短，則更新u --> v的路徑。后面的Dijkstra算法Bellman-Ford算法是基于這個算法的。

Dijkstra算法

算法步驟

1. 創(chuàng)建一個距離列表，其中包含每個節(jié)點到起始節(jié)點的距離。起始節(jié)點的距離設(shè)置為0，其他節(jié)點的距離設(shè)置為無窮大。

2. 創(chuàng)建一個已訪問列表和一個待訪問列表。起始節(jié)點被標記為已訪問，其他所有節(jié)點都被標記為待訪問。

3. 對于每一個待訪問的節(jié)點，計算它到起始節(jié)點的距離。如果這個距離比當前記錄的距離還要短，那么就更新這個節(jié)點的距離。

4. 從待訪問列表中找到距離最小的節(jié)點，將其標記為已訪問，并將其從待訪問列表中移除。

5. 重復(fù)步驟3和4，直到所有的節(jié)點都被訪問過。

6. 距離列表中記錄的就是每個節(jié)點到起始節(jié)點的最短距離。

缺點

無法解決邊值為負值

Bellman-Ford算法

算法步驟

1. 為每個頂點 ’ v '初始化距離數(shù)組 dist[]為dist[v] = INFINITY。假設(shè)任何頂點（假設(shè)為“0”）作為源并分配dist = 0。
2. 根據(jù)以下條件放松所有edges（u，v，weight）N-1次：
   • dist[v] = 最小值(dist[v]，dist[u] + weight)
3. 現(xiàn)在，再次放松所有邊，即第N次，并基于以下兩種情況，我們可以檢測負循環(huán)：
   • 情況 1（存在負循環(huán)）：對于任何邊（u，v，權(quán)重），如果 dist[u] + weight < dist[v]
   • 情況 2（無負循環(huán)）：情況 1 對于所有邊均失敗。

證明

N-1次可以求出最小路徑

Bellman-ford算法思想是，進行一次遍歷，遍歷所有邊，一次一定能找到一個距離start節(jié)點最近的點，N-1次之后，target節(jié)點最多和start節(jié)點之間有N-2個節(jié)點

N次距離減少，出現(xiàn)負循環(huán)回路

負權(quán)重的邊又被遍歷了一次

主定理

將規(guī)模為n的問題轉(zhuǎn)化為a個規(guī)模為n/b的問題，花費的時間是O($n^d$)
T(n)=$a?T(\frac{n}{b})+n^d$, 其中a>1 , b>1 , d>0

• 當 a < $b^d$ , T(n)=O($n^d$)
• 當 a = $b^d$ , T(n)=O($n^{lo{g}_{b}a}?lgn$)
• 當 a > b^d , T(n)=O($n^{lo{g}_{b}a}$)

不想推導(dǎo)，直接記住吧

例子

二分查找

• T(n)=$2T(\frac{n}{2})+1$
• a=2 b=2 d=0 --> O(n)

歸并排序合并

• T(n)=$2T(\frac{n}{2})+n$
• a=2 b=2 d=1 --> O(n*lgn)

遞歸式子

• T(n)=$3T(\frac{n}{4})+nlgn$
• a=3 b=4 d約為1.5 --> O(n*lgn)

紅黑樹

定義

1. 每個節(jié)點要么是黑色，要么是紅色；
2. 根和葉子都是黑色的，所有的葉子都是NIL；
3. 紅色節(jié)點的父節(jié)點是黑色的；
4. 從節(jié)點x到其所有后代葉子節(jié)點的所有路徑中包含相同數(shù)量
   的黑節(jié)點。