數(shù)據(jù)結(jié)構(gòu)
（1）線性表
1）數(shù)組
2）鏈表：單向鏈表干发、雙向鏈表花枫、循環(huán)鏈表庆锦、雙向循環(huán)鏈表上忍、靜態(tài)鏈表腊状。
3）棧：順序棧携御、鏈?zhǔn)綏?
4）隊(duì)列：普通隊(duì)列昌粤、雙向隊(duì)列、阻塞隊(duì)列啄刹、并發(fā)隊(duì)列涮坐、阻塞并發(fā)隊(duì)列。
（2）散列表
1）散列函數(shù)
2）沖突解決：鏈表法誓军、開放地址袱讹、其他
3）動態(tài)擴(kuò)容
4）位圖
（3）樹
1）二叉樹：平衡二叉樹、二叉查找樹谭企、平衡二叉樹（AVL樹廓译、紅黑樹）、完全二叉樹债查、滿二叉樹非区。
2）多路查找樹：B樹、B+樹盹廷、2-3樹征绸、2-3-4樹。
3）堆：小頂堆俄占、大頂堆管怠、優(yōu)先級隊(duì)列、契波那契堆缸榄、二項(xiàng)堆渤弛、可并堆。
4）其他： 樹狀數(shù)組甚带、線段樹她肯、字典樹、后綴樹鹰贵。
（4）圖
1）圖的存儲：臨接矩陣晴氨、臨接表。
2）拓?fù)渑判?
3）最短路徑
4）關(guān)鍵路徑
5）最小生成樹
6）二分圖
7）最大流
8）最短路碉输、最小生成樹籽前、網(wǎng)絡(luò)流建模、最近公共祖先、并查集枝哄。
樹
二叉樹：樹中每個(gè)節(jié)點(diǎn)至多有兩個(gè)子節(jié)點(diǎn)
二叉搜索樹：對于樹中任何節(jié)點(diǎn)肄梨，如果其左子節(jié)點(diǎn)不為空，那么該節(jié)點(diǎn)的value值永遠(yuǎn) >= 其左子節(jié)點(diǎn)膘格；如果其右子節(jié)點(diǎn)不為空峭范，那么該節(jié)點(diǎn)的value值永遠(yuǎn) <= 其右子節(jié)點(diǎn)
滿二叉樹：樹中除了葉子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)
完全二叉樹：在滿足滿二叉樹的性質(zhì)后瘪贱，最后一層的葉子節(jié)點(diǎn)均需在最左邊
完美二叉樹：滿足完全二叉樹性質(zhì)纱控，樹的葉子節(jié)點(diǎn)均在最后一層（也就是形成了一個(gè)完美的三角形）
滿二叉樹、完全二叉樹菜秦、完美二叉樹的定義是越來越嚴(yán)格的
AVL 樹
AVL樹本質(zhì)上還是一個(gè)二叉搜索樹甜害，不過比二叉搜索樹多了一個(gè)平衡條件：每個(gè)節(jié)點(diǎn)的左右子樹的高度差不大于1。
二叉樹的應(yīng)用是為了彌補(bǔ)鏈表的查詢效率問題球昨，但是極端情況下尔店，二叉搜索樹會無限接近于鏈表，這種時(shí)候就無法體現(xiàn)二叉搜索樹在查詢時(shí)的高效率主慰，而最初出現(xiàn)的解決方式就是AVL樹嚣州。
因?yàn)槎樗阉鳂涞囊螅宰裱璿ale從小到大：左-> 中 ->右共螺， 搜索的時(shí)候效率很高该肴。
紅黑樹，因?yàn)橹皇菨M足平衡二叉樹的左右兩個(gè)子樹高度差只有1的差距藐不，所以插入和刪除的效率更高匀哄，搜索的效率角度。
LSM
LSM 樹
LSM（Log-Structured Merge-Trees）和 B+ 樹相比雏蛮，是犧牲了部分讀的性能來換取寫的性能(通過批量寫入)涎嚼，實(shí)現(xiàn)讀寫之間的涩笤。 Hbase蛾坯、LevelDB、Tair（Long DB）妈候、nessDB 采用 LSM 樹的結(jié)構(gòu)犀概。LSM可以快速建立索引立哑。
B+ 樹讀性能好，但由于需要有序結(jié)構(gòu)阱冶，當(dāng)key比較分散時(shí)，磁盤尋道頻繁滥嘴，造成寫性能木蹬。
LSM 是將一個(gè)大樹拆分成N棵小樹，先寫到內(nèi)存（無尋道問題，性能高）镊叁，在內(nèi)存中構(gòu)建一顆有序小樹（有序樹）尘颓，隨著小樹越來越大，內(nèi)存的小樹會flush到磁盤上晦譬。當(dāng)讀時(shí)疤苹，由于不知道數(shù)據(jù)在哪棵小樹上，因此必須遍歷（二分查找）所有的小樹敛腌，但在每顆小樹內(nèi)部數(shù)據(jù)是有序的卧土。
《LSM樹（Log-Structured Merge Tree）存儲引擎》
極端的說，基于LSM樹實(shí)現(xiàn)的HBase的寫性能比MySQL高了一個(gè)數(shù)量級像樊，讀性能低了一個(gè)數(shù)量級尤莺。
優(yōu)化方式：Bloom filter 替代二分查找；compact 小數(shù)位大樹生棍，提高查詢性能颤霎。
Hbase 中，內(nèi)存中達(dá)到一定閾值后涂滴，整體flush到磁盤上友酱、形成一個(gè)文件（B+數(shù)），HDFS不支持update操作柔纵，所以Hbase做整體flush而不是merge update缔杉。flush到磁盤上的小樹，定期會合并成一個(gè)大樹首量。
二叉樹
主要語義
- 普通平衡樹的廣度遍歷和深度遍歷和鏈表相比壮吩，相同的是存在不穩(wěn)定性。不同的是最好的性能是logN, 最壞是n加缘。
2. 二叉查找樹最大特性是鸭叙，左子樹關(guān)鍵字 < 根節(jié)點(diǎn)關(guān)鍵字 < 柚子樹關(guān)鍵字。這樣能保證查找的時(shí)候是穩(wěn)定的logN拣宏。 但是為了保存二叉樹的特征沈贝，在插入和刪除的時(shí)候，需要做必要的旋轉(zhuǎn)勋乾。
AVL是強(qiáng)平衡二叉查找樹宋下， 查找的性能最穩(wěn)定，數(shù)的高度也最低辑莫，但是插入和刪除的時(shí)候学歧，旋轉(zhuǎn)太耗時(shí)。
紅黑樹是弱平衡樹各吨， 插入和刪除的時(shí)候只需要達(dá)到紅黑相間隔以及二叉樹特性枝笨，故相對性能較好。 同時(shí)紅黑的特征了也優(yōu)化了查找路徑，增加了約束横浑，避免二叉樹旋轉(zhuǎn)N次后成為極端的線性鏈剔桨。
b樹和b+樹是多路查找樹，也是平衡樹徙融。相當(dāng)于在之前的二叉樹增加一級索引：每一層允許關(guān)鍵字M洒缀，允許出現(xiàn)[2,M]個(gè)子節(jié)點(diǎn)，允許非葉子節(jié)點(diǎn)有關(guān)鍵字和指向子節(jié)點(diǎn)的指針欺冀，插入的時(shí)候不一定需要通過旋轉(zhuǎn)來實(shí)現(xiàn)树绩。 這樣在非常復(fù)雜和龐大的基數(shù)數(shù)據(jù)中，可以極大的降低樹的高度脚猾，增加查詢和插入的性能葱峡。缺點(diǎn)就是單節(jié)點(diǎn)的計(jì)算邊復(fù)雜了，如果cpu的計(jì)算能力很強(qiáng)的情況下龙助，這點(diǎn)可以忽略砰奕。
6. b+數(shù)和b樹的區(qū)別是b+樹在b樹的基礎(chǔ)上優(yōu)化了索引，使索引和關(guān)鍵字分開提鸟，且關(guān)鍵字只存在于葉子節(jié)點(diǎn)军援，簡化了每一個(gè)節(jié)點(diǎn)的計(jì)算，當(dāng)m變大的時(shí)候称勋，優(yōu)化程度越大胸哥；并且在增加和刪除關(guān)鍵字的直接和存儲卷功能相關(guān)，因?yàn)槲募到y(tǒng)中是按頁和塊存儲的赡鲜， b樹的數(shù)據(jù)變更存在跨多個(gè)頁和塊空厌，而b+樹是存在于樹的葉子節(jié)點(diǎn)是，可以是連續(xù)存儲空間银酬，增加和刪除都是性能很高的嘲更。 b+樹在葉子節(jié)點(diǎn)增加了鏈指針，可以指向關(guān)鍵字代表的行記錄或塊記錄揩瞪。
旋轉(zhuǎn)
b++插入和刪除時(shí)涉及到葉子節(jié)點(diǎn)和索引節(jié)點(diǎn)的拆分赋朦、合并，索引下沉問題李破。在兄弟節(jié)點(diǎn)有富余宠哄，但是索引節(jié)點(diǎn)滿的情況下還會 產(chǎn)生旋轉(zhuǎn)。
https://blog.csdn.net/sunshine_lyn/article/details/82747596
二叉查找樹
簡介
二叉查找樹也稱為有序二叉查找樹,滿足二叉查找樹的一般性質(zhì),是指一棵空樹具有如下性質(zhì):
任意節(jié)點(diǎn)左子樹不為空,則左子樹的值均小于根節(jié)點(diǎn)的值.*
任意節(jié)點(diǎn)右子樹不為空,則右子樹的值均大于于根節(jié)點(diǎn)的值.*
任意節(jié)點(diǎn)的左右子樹也分別是二叉查找樹.*
沒有鍵值相等的節(jié)點(diǎn).*
參考：
https://www.cnblogs.com/feng9exe/p/8920738.html
B樹特性
B樹的性質(zhì)
定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子嗤攻；且M>2毛嫉；
根結(jié)點(diǎn)的兒子數(shù)為[2, M]；
除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M]妇菱；
每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1（取上整）和至多M-1個(gè)關(guān)鍵字承粤；（至少2個(gè)關(guān)鍵字）
非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=指向兒子的指針個(gè)數(shù)-1惊畏；
非葉子結(jié)點(diǎn)的關(guān)鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]密任；
非葉子結(jié)點(diǎn)的指針：P[1], P[2], …, P[M]；其中P[1]指向關(guān)鍵字小于K[1]的子樹偷俭，P[M]指向關(guān)鍵字大于K[M-1]的子樹浪讳，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹；
所有葉子結(jié)點(diǎn)位于同一層涌萤；
B+樹特性
B+樹的性質(zhì)(下面提到的都是和B樹不相同的性質(zhì))
非葉子節(jié)點(diǎn)的子樹指針與關(guān)鍵字個(gè)數(shù)相同;
非葉子節(jié)點(diǎn)的子樹指針p[i],指向關(guān)鍵字值屬于[k[i],k[i+1]]的子樹.(B樹是開區(qū)間,也就是說B樹不允許關(guān)鍵字重復(fù),B+樹允許重復(fù))淹遵；
為所有葉子節(jié)點(diǎn)增加一個(gè)鏈指針.
所有關(guān)鍵字都在葉子節(jié)點(diǎn)出現(xiàn)(稠密索引). (且鏈表中的關(guān)鍵字恰好是有序的);
非葉子節(jié)點(diǎn)相當(dāng)于是葉子節(jié)點(diǎn)的索引(稀疏索引),葉子節(jié)點(diǎn)相當(dāng)于是存儲(關(guān)鍵字)數(shù)據(jù)的數(shù)據(jù)層.
更適合于文件系統(tǒng);
B-樹是一種平衡的多路查找(又稱排序)樹，在文件系統(tǒng)中有所應(yīng)用负溪。主要用作文件的索引透揣。其中的B就表示平衡(Balance)
B+樹有一個(gè)最大的好處，方便掃庫川抡，B樹必須用中序遍歷的方法按序掃庫辐真，而B+樹直接從葉子結(jié)點(diǎn)挨個(gè)掃一遍就完了。
B+樹支持range-query(區(qū)間查詢)非常方便崖堤，而B樹不支持侍咱。這是數(shù)據(jù)庫選用B+樹的最主要原因。
比如要查 5-10之間的密幔，B+樹一把到5這個(gè)標(biāo)記楔脯，再一把到10，然后串起來就行了胯甩，B樹就非常麻煩昧廷。B樹的好處，就是成功查詢特別有利偎箫，因?yàn)闃涞母叨瓤傮w要比B+樹矮木柬。不成功的情況下，B樹也比B+樹稍稍占一點(diǎn)點(diǎn)便宜镜廉。B樹的優(yōu)勢是當(dāng)你要查找的值恰好處在一個(gè)非葉子節(jié)點(diǎn)時(shí)弄诲，查找到該節(jié)點(diǎn)就會成功并結(jié)束查詢，而B+樹由于非葉節(jié)點(diǎn)只是索引部分娇唯，這些節(jié)點(diǎn)中只含有其子樹中的最大(或最小)關(guān)鍵字齐遵，當(dāng)非終端節(jié)點(diǎn)上的關(guān)鍵字等于給點(diǎn)值時(shí)，查找并不終止塔插，而是繼續(xù)向下直到葉子節(jié)點(diǎn)梗摇。因此在B+樹中，無論查找成功與否想许，都是走了一條從根到葉子節(jié)點(diǎn)的路徑伶授。mysql底層存儲是用B+樹實(shí)現(xiàn)的断序，因?yàn)閮?nèi)存中B+樹是沒有優(yōu)勢的，但是一到磁盤糜烹，B+樹的威力就出來了违诗。
B*樹
是B+樹的變體，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針疮蹦；B樹定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)M诸迟，即塊的最低使用率為2/3（代替B+樹的1/2）；
B+樹的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)愕乎，分配一個(gè)新的結(jié)點(diǎn)阵苇，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針感论；B+樹的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)绅项，而不會影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟的指針比肄；
B*樹的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)快耿，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中芳绩，再在原結(jié)點(diǎn)插入關(guān)鍵字润努，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了）；如果兄弟也滿了示括，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)铺浇，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針垛膝；
所以鳍侣，B樹分配新結(jié)點(diǎn)的概率比B+樹要低，空間使用率更高吼拥；*
B-樹
1970年倚聚，R.Bayer和E.mccreight提出了一種適用于外查找的樹，它是一種平衡的多叉樹凿可，稱為B樹（或B-樹惑折、B_樹）。
一棵m階B樹(balanced tree of order m)是一棵平衡的m路搜索樹枯跑。它或者是空樹惨驶，或者是滿足下列性質(zhì)的樹：
1、根結(jié)點(diǎn)至少有兩個(gè)子女敛助；
2粗卜、每個(gè)非根節(jié)點(diǎn)所包含的關(guān)鍵字個(gè)數(shù) j 滿足：┌m/2┐ - 1 <= j <= m - 1；
3纳击、除根結(jié)點(diǎn)以外的所有結(jié)點(diǎn)（不包括葉子結(jié)點(diǎn)）的度數(shù)正好是關(guān)鍵字總數(shù)加1续扔，故內(nèi)部子樹個(gè)數(shù) k 滿足：┌m/2┐ <= k <= m 攻臀；
4、所有的葉子結(jié)點(diǎn)都位于同一層纱昧。
是一種多路搜索樹（并不是二叉的）：
1.定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子刨啸；且M>2；
2.根結(jié)點(diǎn)的兒子數(shù)為[2, M]识脆；
3.除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M]呜投；
4.每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1（取上整）和至多M-1個(gè)關(guān)鍵字；（至少2個(gè)關(guān)鍵字）
5.非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=指向兒子的指針個(gè)數(shù)-1存璃；
6.非葉子結(jié)點(diǎn)的關(guān)鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]雕拼；
7.非葉子結(jié)點(diǎn)的指針：P[1], P[2], …, P[M]纵东；其中P[1]指向關(guān)鍵字小于K[1]的
子樹，P[M]指向關(guān)鍵字大于K[M-1]的子樹啥寇，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹偎球；
8.所有葉子結(jié)點(diǎn)位于同一層；
算法
算法分析
（1）復(fù)雜度分析
1）空間復(fù)雜度
2）時(shí)間復(fù)雜度：最好辑甜、最壞衰絮、平均、均攤磷醋。
（2）基本算法思想：貪心算法猫牡、分治算法、動態(tài)規(guī)劃邓线、回溯算法淌友、枚舉算法、倍增骇陈、二分震庭。
算法實(shí)現(xiàn)
（1）排序
1）O(n^2)：冒泡、插入你雌、選擇器联、希爾。
2）O(NlogN)：歸并婿崭、快速拨拓、堆
3）O(n)：計(jì)數(shù)、基數(shù)氓栈、桶千元。
（2）搜索：深度優(yōu)先搜索、廣度優(yōu)先搜索颤绕、A*啟發(fā)式搜索幸海。
（3）查找：線性表查找祟身、樹結(jié)果查找、散列表查找物独。
（4）字符串匹配：樸素袜硫、KMP、Robin-Karp挡篓、Boyer-Moore婉陷、AC自動機(jī)、Trie官研、后綴數(shù)組秽澳。
（5）其他：數(shù)論、計(jì)算幾何戏羽、概率分析担神、并查集、拓?fù)渚W(wǎng)絡(luò)始花、矩陣運(yùn)算妄讯、線性規(guī)劃。
回溯算法
https://segmentfault.com/a/1190000018319044?utm_source=tag-newest
前綴樹
https://www.cnblogs.com/luosongchao/p/3239521.html
深度優(yōu)先和廣度優(yōu)先
https://www.cnblogs.com/whywhy/p/4888632.html
動態(tài)規(guī)劃
動態(tài)規(guī)劃的解題核心主要分為兩步：
第一步：狀態(tài)的定義
第二步：狀態(tài)轉(zhuǎn)移方程的定義
在這里酷宵，我們?yōu)榱吮苊饣煜谩盃顟B(tài)”這個(gè)詞來替代“問題”這個(gè)詞亥贸。“問題”表示的含義類似：題目浇垦、要求解的內(nèi)容炕置、題干中的疑問句這樣的概念。狀態(tài)表示我們在求解問題之中對問題的分析轉(zhuǎn)化男韧。
第一步：狀態(tài)的定義
有的問題過于抽象讹俊，或者過于啰嗦干擾我們解題的思路，我們要做的就是將題干中的問題進(jìn)行轉(zhuǎn)化（換一種說法煌抒，含義不變）仍劈。轉(zhuǎn)化成一系列同類問題的某個(gè)解的情況，比如說：
題目：求一個(gè)數(shù)列中最大連續(xù)子序列的和寡壮。
我們要將這個(gè)原問題轉(zhuǎn)化為：
狀態(tài)定義：Fk是第k項(xiàng)前的最大序列和贩疙，求F1～FN中最大值。
通過換一種表述方式况既，我們清晰的發(fā)現(xiàn)了解決問題的思路这溅，如何求出F1～FN中的最大值是解決原問題的關(guān)鍵部分。上述將原問題轉(zhuǎn)化成另一種表述方式的過程叫做：狀態(tài)的定義棒仍。這樣的狀態(tài)定義給出了一種類似通解的思路悲靴，把一個(gè)原來毫無頭緒的問題轉(zhuǎn)換成了可以求解的問題。
第二步：狀態(tài)轉(zhuǎn)移方程的定義
在進(jìn)行了狀態(tài)的定義后莫其，自然而然的想到去求解F1～FN中最大值癞尚。這也是狀態(tài)定義的作用耸三，讓我們把一個(gè)總體的問題轉(zhuǎn)化成一系列問題，而第二步：狀態(tài)轉(zhuǎn)移方程的定義則告訴我們?nèi)绾稳デ蠼庖粋€(gè)問題浇揩，對于上述已經(jīng)轉(zhuǎn)換成一系列問題我們要關(guān)注的點(diǎn)就在于：如何能夠用前一項(xiàng)或者前幾項(xiàng)的信息得到下一項(xiàng)仪壮，這種從最優(yōu)子狀態(tài)轉(zhuǎn)換為下一個(gè)最優(yōu)狀態(tài)的思路就是動態(tài)規(guī)劃的核心。
對于上面的例子題目來說胳徽，狀態(tài)轉(zhuǎn)移方程的定義應(yīng)該是：
Fk=max{Fk-1+Ak,Ak}
Fk是前k項(xiàng)的和积锅，Ak是第k項(xiàng)的值
仔細(xì)思考一番，我們能夠得到這樣的結(jié)論养盗，對于前k個(gè)項(xiàng)的最大子序列和是前k-1項(xiàng)的最大子序列和Fk與第k項(xiàng)的和缚陷、或者第k項(xiàng)兩者中較大的。如果大家還是不能理解這個(gè)原理建議用演算紙自己計(jì)算一番往核，這里就不過多贅述了箫爷。這種狀態(tài)轉(zhuǎn)移的思路就是DP的核心。
動態(tài)規(guī)劃
動態(tài)規(guī)劃（英語：Dynamic programming铆铆，簡稱 DP）是一種在數(shù)學(xué)、管理科學(xué)丹喻、計(jì)算機(jī)科學(xué)薄货、經(jīng)濟(jì)學(xué)和生物信息學(xué)中使用的，通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法碍论。
動態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題谅猾，動態(tài)規(guī)劃方法所耗時(shí)間往往遠(yuǎn)少于樸素解法。
動態(tài)規(guī)劃背后的基本思想非常簡單鳍悠。大致上税娜，若要解一個(gè)給定問題，我們需要解其不同部分（即子問題）藏研，再根據(jù)子問題的解以得出原問題的解敬矩。動態(tài)規(guī)劃往往用于優(yōu)化遞歸問題，例如斐波那契數(shù)列蠢挡，如果運(yùn)用遞歸的方式來求解會重復(fù)計(jì)算很多相同的子問題弧岳，利用動態(tài)規(guī)劃的思想可以減少計(jì)算量。
通常許多子問題非常相似业踏，為此動態(tài)規(guī)劃法試圖僅僅解決每個(gè)子問題一次禽炬，具有天然剪枝的功能，從而減少計(jì)算量：一旦某個(gè)給定子問題的解已經(jīng)算出勤家，則將其記憶化存儲腹尖，以便下次需要同一個(gè)子問題解之時(shí)直接查表。這種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長時(shí)特別有用
貪心算法
記錄中間狀態(tài)伐脖，拆解子問題热幔、子狀態(tài)乐设，當(dāng)前決策是否影響后續(xù)的決策。尋求最優(yōu)解断凶。
如何拆解子問題
按串行任務(wù)分
時(shí)間串行的任務(wù)伤提，按子任務(wù)來分解，即每一步都是在前一步的基礎(chǔ)上再選擇當(dāng)前的最優(yōu)解认烁。
按規(guī)模遞減分
規(guī)模較大的復(fù)雜問題肿男，可以借助遞歸思想（見第2課），分解成一個(gè)規(guī)模小一點(diǎn)點(diǎn)的問題却嗡，循環(huán)解決舶沛，當(dāng)最后一步的求解完成后就得到了所謂的“全局最優(yōu)解”。
按并行任務(wù)分
這種問題的任務(wù)不分先后窗价，可能是并行的如庭，可以分別求解后，再按一定的規(guī)則（比如某種配比公式）將其組合后得到最終解撼港。
動態(tài)規(guī)劃和貪心
動態(tài)規(guī)劃可以用到回溯坪它， 也可以用記憶法來優(yōu)化重復(fù)計(jì)算。
動態(tài)規(guī)劃是一種自頂向下的方法帝牡。
貪心法是一種自底向上的方法往毡，避免回溯。也就是從解向起始條件靠近
KMP算法
https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html
