做網(wǎng)站空間500m多少錢推廣下載app賺錢
截圖摘自湖南大學彭鵬老師的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ī)劃還一定是正確的。
- 對任務(wù)按照結(jié)束時間排序
- 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)
用人話說就是:
- 對任意一個節(jié)點A做DFS, 直到終點到了A,對遍歷的邊進行標記,把所有遍歷的邊去除。
- 對任意一個還有邊的點B進行DFS,重復(fù)操作,直到所有邊都被標記。
- 標記的邊就是歐拉回路。
拓撲排序
算法步驟
- 找到所有入度為0的節(jié)點,并加入隊列
- 依次從隊列中取出節(jié)點,并將其指向的節(jié)點的入度減1,如果減1后,該節(jié)點的入度為0,則將其加入隊列
最小生成樹
把所有點都連接起來,使得生成樹各邊權(quán)值之和最小。
prim算法
算法步驟
- 選擇一個節(jié)點作為起始點,并將其加入生成樹中。
- 選擇與生成樹相連的,最小的邊,將其加入生成樹中。
- 重復(fù)步驟2,直到所有節(jié)點都被加入生成樹中。
復(fù)雜度
- 使用鄰接矩陣表示圖: O(V^2) V是頂點數(shù)量,每次都要找最小的頂點
- 使用鄰接表表示圖: O(ElogV) E是邊的數(shù)量,每次都要找最小的頂點
(加入新節(jié)點的時候,把新節(jié)點所有相鄰的,不在生成樹中的邊添加進去)
Kruskal算法
算法步驟
- 按照邊的權(quán)值從小到大排序
- 依次選擇邊,如果選擇后不會形成環(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算法
算法步驟
-
創(chuàng)建一個距離列表,其中包含每個節(jié)點到起始節(jié)點的距離。起始節(jié)點的距離設(shè)置為0,其他節(jié)點的距離設(shè)置為無窮大。
-
創(chuàng)建一個已訪問列表和一個待訪問列表。起始節(jié)點被標記為已訪問,其他所有節(jié)點都被標記為待訪問。
-
對于每一個待訪問的節(jié)點,計算它到起始節(jié)點的距離。如果這個距離比當前記錄的距離還要短,那么就更新這個節(jié)點的距離。
-
從待訪問列表中找到距離最小的節(jié)點,將其標記為已訪問,并將其從待訪問列表中移除。
-
重復(fù)步驟3和4,直到所有的節(jié)點都被訪問過。
-
距離列表中記錄的就是每個節(jié)點到起始節(jié)點的最短距離。
缺點
無法解決邊值為負值
Bellman-Ford算法
算法步驟
- 為每個頂點 ’ v '初始化距離數(shù)組 dist[]為dist[v] = INFINITY。假設(shè)任何頂點(假設(shè)為“0”)作為源并分配dist = 0。
- 根據(jù)以下條件放松所有edges(u,v,weight)N-1次:
- dist[v] = 最小值(dist[v],dist[u] + weight)
- 現(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 n^d nd)
T(n)= a ? T ( n b ) + n d a*T(\frac{n})+n^d a?T(bn?)+nd, 其中a>1 , b>1 , d>0
- 當 a < b d b^d bd , T(n)=O( n d n^d nd)
- 當 a = b d b^d bd , T(n)=O( n l o g b a ? l g n n^{log_ a}*lgn nlogb?a?lgn)
- 當 a > b^d , T(n)=O( n l o g b a n^{log_ a} nlogb?a)
不想推導(dǎo),直接記住吧
例子
二分查找
- T(n)= 2 T ( n 2 ) + 1 2T(\frac{n}{2})+1 2T(2n?)+1
- a=2 b=2 d=0 --> O(n)
歸并排序合并
- T(n)= 2 T ( n 2 ) + n 2T(\frac{n}{2})+n 2T(2n?)+n
- a=2 b=2 d=1 --> O(n*lgn)
遞歸式子
- T(n)= 3 T ( n 4 ) + n l g n 3T(\frac{n}{4})+nlg{n} 3T(4n?)+nlgn
- a=3 b=4 d約為1.5 --> O(n*lgn)
紅黑樹
定義
- 每個節(jié)點要么是黑色,要么是紅色;
- 根和葉子都是黑色的,所有的葉子都是NIL;
- 紅色節(jié)點的父節(jié)點是黑色的;
- 從節(jié)點x到其所有后代葉子節(jié)點的所有路徑中包含相同數(shù)量
的黑節(jié)點。