一、算法與問題
算法是解決問題的一系列步驟；
理解問題，設計算法的一般過程：
解決問題的時候可以首先考慮蠻力法，因為蠻力法一般都能解決，只是效率比較低。使用蠻力法解決問題之後可以再考慮使用其他算法思想進行優化。在使用蠻力法的時候如果解決起來比較費力，可以再次思考一下問題，看看能不能找到什麼規律，然後，在該規律之上再求解。
蠻力法往往需要從頭到尾遍歷所有的可能，而且有時候一個問題可能會有好幾種遍歷策略，有的策略能夠得到問題的解，有一些不能導出最終問題的解，所以，使用蠻力法的時候遍歷策略的選擇往往是很重要的。好的遍歷策略甚至能起到跟貪婪，動態規劃策略一樣的作用，從這個意義上來說貪婪，動態規劃，回溯，分支界限也算是一種蠻力法，只不過是聰明的蠻力法。
優化的思路有以下 3 個方向：
1、蠻力法 ---> 貪婪，動態規劃 ---> 回溯，分支界限
2、分治，減治，變治
3、時空權衡
二、蠻力法
蠻力法是一種簡單直觀的解決問題的辦法，常常直接基於問題的描述和所涉及的概念。蠻力法所能解決的問題域也是最廣的，但是效率往往不高；
使用蠻力法的算法有：
1、冒泡排序，選擇排序
2,、順序匹配
3、窮舉法
三、分治法
分治法設計步驟：
1、將問題實例劃分為同一問題的較小的實例，最好擁有同樣的規模；
2、求解較小的實例；
3、合併較小問題的解；
分治法算法：
1、歸並排序，快速排序
2、折半查找
3、二叉樹遍歷（前序，中序，後序）
4、大整數乘法和矩陣乘法的分治
5、最近對和凸包問題的分治
四、減治法
減治技術應用了問題的解和同樣問題較小實例的解之間的關係，減治法主要有一下三種：
1、減去一個常量 每次減去一個規模相同的常量，一般等於 1 或者 2，例如求 a 的 n 次方可以理解為 f (n)=f (n-1)*a
2、減去一個常量因子 每次迭代減去相同的常數因子，例如每次把問題規模變為原來問題的 1/2，還是求 a 的 n 次方，但是可以這樣寫遞歸公式；
3、減去的規模是可變的 每次迭代減去的問題規模是可變的，例如求最大公約數 gcd (m,n) = gcd (n,m mod n)，還有基於快速排序查找第 k 大的數；
減治法算法（減常量）
插入排序、深度優先查找、廣度優先查找、拓撲排序、生成排列組合、生成子集
減常因子算法
假幣問題、約舍夫斯問題
減可變規模
基於快速排序查找第 k 大的數、插值查找、二叉查找樹的插入和查找
五、變治法
變治主要體現在變換問題實例上，主要有 3 中類型：
1、問題化簡：變換為同樣問題一個更簡單更方便的實例
2、改變表現：同樣問題實例的不同表現
3、問題變換：變換為另一個問題的實例
問題化簡： 預排序，高斯消去
改變表現：查找樹、堆排序
問題變換：
1、最小公倍數：把求最下公倍數轉換為求最大公約數
lcm(m,n) = m*n/gcd(m,n)
六、時空權衡
空間換時間，動態規劃和散列也是空間換時間的一種體現
1、計數排序
2、字符串匹配 Horspool, Boyer-Moore, KMP
3、散列
4、B 樹索引
七、動態規劃
動態規劃的出現是用來解決交疊子問題的重複求解問題，具體的求解過程一般分以下兩步：
1、確定遞推關係
2、根據問題性質採取合適的規劃策略，自底向上遞推或是自頂向下記憶化搜索
記憶化搜索也要維護一張狀態表格，但每次要計算新值的時候會先查找表格該值是否計算過，如果已經計算過就直接用，否則遞歸計算。
動態規劃算法：
1、計算二項係數
C(n,k) = C(n-1,k-1)+C(n-2,k)
2、Warshall 算法計算傳遞閉包
3、Floyd 算法計算完全最短路徑
4、最優二叉樹構造
5、背包
八、貪婪
所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。在動態規劃算法中，每步所作的選擇往往依賴於相關子問題的解。因而只有在解出相關子問題後，才能作出選擇。而在貪心算法中，僅在當前狀態下作出最好選擇，即局部最優選擇。然後再去解作出這個選擇後產生的相應的子問題。貪心算法所作的貪心選擇可以依賴於以往所作過的選擇，但決不依賴於將來所作的選擇，也不依賴於子問題的解。正是由於這種差別，動態規劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為一個規模更小的子問題。
貪婪算法：
1、Prim，Kruskal 算法求最小生成樹
2、Dijkstra 算法
3、Huffman
九、迭代改進
從某些可行解出發，然後重複應用一些簡單的步驟不斷改進它:
1、構造可行解；
2、檢查當前解是不是最優的，如果不是，替換它；
迭代改進算法：
1、單純形法與線性規劃
2、最大流
3、遞歸下降
4、穩定婚姻
5、EM
6、二分圖匹配
十、回溯法與分治界限法
其實所謂的狀態空間樹也就是一顆決策樹，每一個決策節點也就是一次迭代，通過對決策樹不斷地減枝，生長，推導出最終結果；
其應用過程如下:
1、確定遍歷規律，也就是決策樹的生長順序；
2、通過回溯或分支界限不斷地對樹進行生長，減枝；
回溯算法應用：
1、n 皇后問題
2、哈密頓回路
3、生成子集
分支界限：
1、背包
2、旅行商