幾種算法思想概要

動态規劃（Dynamic programming）

https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92

https://blog.csdn.net/u013445530/article/details/40210587

是一種在數學、管理科學、計算機科學、經濟學和生物資訊學中使用的，通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。

動态規劃常常适用于有重疊子問題[1]和最優子結構性質的問題，動态規劃方法所耗時間往往遠少于樸素解法。

動态規劃背後的基本思想非常簡單。大緻上，若要解一個給定問題，我們需要解其不同部分（即子問題），再根據子問題的解以得出原問題的解。

通常許多子問題非常相似，為此動态規劃法試圖僅僅解決每個子問題一次，進而減少計算量：一旦某個給定子問題的解已經算出，則将其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重複子問題的數目關于輸入的規模呈指數增長時特别有用。

動态規劃在查找有很多重疊子問題的情況的最優解時有效。它将問題重新組合成子問題。為了避免多次解決這些子問題，它們的結果都逐漸被計算并被儲存，從簡單的問題直到整個問題都被解決。是以，動态規劃儲存遞歸時的結果，因而不會在解決同樣的問題時花費時間。

動态規劃隻能應用于有最優子結構的問題。最優子結構的意思是局部最優解能決定全局最優解（對有些問題這個要求并不能完全滿足，故有時需要引入一定的近似）。簡單地說，問題能夠分解成子問題來解決。

執行個體：斐波那契數列（Fibonacci polynomial），最長公共子序列，01背包問題

迪傑斯特拉算（Dijkstra's algorithm）

戴克斯特拉算法使用了廣度優先搜尋解決賦權有向圖的單源最短路徑問題。該算法存在很多變體；戴克斯特拉的原始版本找到兩個頂點之間的最短路徑，但是更常見的變體固定了一個頂點作為源節點然後找到該頂點到圖中所有其它節點的最短路徑，産生一個最短路徑樹。該算法常用于路由算法或者作為其他圖算法的一個子子產品。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示城市間開車行經的距離，該算法可以用來找到兩個城市之間的最短路徑。

https://zh.wikipedia.org/wiki/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95

https://www.zhihu.com/question/22311234

梯度提升樹

梯度提升樹（GBT），還可以稱為梯度提升決策樹（GBDT）、梯度提升回歸樹（GBRT）等。是應用非常廣泛的機器學習算法。GBDT屬于內建學習boosting算法，其弱學習器可使用CART決策