1. 9.2 回溯演算法的例子
在4 * 4的方格棋盤上放置4個皇後棋子，使得沒有兩個皇後在同一行、同一列，也不在同一條45度的斜線上， 問有多少種布局?
回溯演算法的解一般是向量，而這個題也不例外，設4維向量的<x1,x2,x3,x4>，Xi中i表示第幾個皇後，Xi表示在棋盤第i行的位置，比如其中一個解是<2,4,1,3>，如下圖
1.四皇後問題中，葉節點就是一個解。
2.四皇後每一個節點的子樹代表著下一個皇後可以放的列數，因為都是n，所以子樹都是n叉樹，故四皇後是一顆 n叉樹
3.四皇後的解至少有兩個，因為棋盤可以沿著中心線翻折
有n種物品，每種物品只有1個。第i種物品價值為vi，重量為wi，i=1，2，3...n. 問如何選擇放入背包的物品，使得總重量不超過B，而價值達到最大?
同樣，此問題的解可用一個向量來表示，該向量就代表了所有的物品，如果對應物品為1，則表示裝入背包，反之，沒有被裝入。
因此，回溯的每層可以表示為對應的物品，分支左右可以表示取或者不取（向量中表示為1或0）
總而言之，每一個節點也就是物品只有0和1兩種狀態，因此該樹一棵二叉樹，或者為 子集樹
1.選擇第一個物品，目前總重量為8，總價值為12。
2.再選擇第二個物品，總重量為14 > 13，觸發回溯。
3.不選擇第二個物品，選擇第三個商品，總重量是12，總價值為21。
4.再選擇第四個物品，總重量為15 > 13，觸發回溯。
5.不選擇第四個物品，總重量為12，總價值為21，與目前最優解價值進行比較，如果最優解價值大於21則替換目前的最優解向量和最優解價值。
1.背包問題只有在葉節點才能生成一個滿足條件的解，而之後將該解和最優解比較。
2.背包問題必須遍歷完所有的分支，才能夠獲得最終的解。
3.背包問題是一顆子集樹。
有n個城市，已知任兩個城市之間的距離， 求一條每個城市恰好經過一次的迴路，使得總長度最小 。
貨郎問題中主要的一點就是每一個點（除了第一個點）其他點必須經過且只能經過1次，這就很像數學中的排列。
因此，我們採用一個向量來表示貨郎問題的城市排列
1.貨郎問題是一顆分支不斷減少的排列數（和數學的排列類似）
2.貨郎問題也得遍歷完所有的情況，比較後得出最優解。
1.解都是用向量表示
2.搜索空間都是樹
3.搜索策略多種，有深度優先、寬度優先和跳躍式遍歷搜索樹。
2. 六、遞歸與回溯演算法
在計算機領域裡面，很多問題都可以要採用遞歸演算法來解決。遞歸中，最長用到的方法就是回溯法。我們具體分析問題的時候，可以發現這類問題本質是一個樹的形狀。
遞歸演算法的本質還是將原來的問題轉化為了更小的同一問題，進行解決。一般注意兩點：
1、遞歸終止的條件。對應到了遞歸演算法中最基本的問題，也是最最簡單的問題。
2、遞歸過程。遞歸過程需要將原問題一步一步的推到更小的 同一 問題，更小的意思就是子問題解決起來就更加的簡單。有寫情況是能夠找到一個遞推的公式的。這個過程中就需要透徹的去理解遞歸函數的意義。明確這個函數的輸入和輸出是什麼，這樣來寫的話，就清晰多了。
因為有了這樣的遞歸公式，那麼我們就很容易的能看出來遞歸的終止條件就是我們知道的f(0)和f(1)了。有了f(0)和f(1)之後，我們就能夠繼續的遞推出f(3)一直到f(n)了。
但是我們現在才用一個遞歸演算法的思想來解決這個問題:
像我們常見的數據結構如鏈表、樹、圖等都是有著天然的遞歸結構的，鏈表由於是一個線性的結構，那麼通常我們也是能夠直接循環遍歷就能解決問題的，但是這里我們用遞歸法來解決一下LeetCode上面的問題
LeetCode 203 移除鏈表元素
分析：鏈表的結構可以理解成一個節點連接這一個更短的鏈表，這樣依次一直看下去，直到最後一個節點None，那麼我們這個時候的遞歸終止條件就是head指向None了，返回的就是None
深入的理解遞歸演算法之後，我們就開始進行回溯法的學習。通過LeetCode上面的幾道題，我們來深入的探討一下遞歸與回溯法的應用。
持續更新中...
數據結構與演算法系列博客：
一、數據結構與演算法概述
二、數組及LeetCode典型題目分析
三、鏈表（Linked list）以及LeetCode題
四、棧與隊列（Stack and Queue
五、樹（Trees）
六、遞歸與回溯演算法
七、動態規劃
八、排序與搜索
九、哈希表
參考資料
1、
2、
3、
3. 回溯演算法與貪心演算法
回溯是遞歸的副產品，只要有遞歸就會有回溯 ，所以回溯法也經常和二叉樹遍歷，深度優先搜索混在一起，因為這兩種方式都是用了遞歸。
回溯法就是暴力搜索，並不是什麼高效的演算法，最多再剪枝一下。
回溯演算法能解決如下問題：
組合問題：N個數裡面按一定規則找出k個數的集合
排列問題：N個數按一定規則全排列，有幾種排列方式
切割問題：一個字元串按一定規則有幾種切割方式
子集問題：一個N個數的集合里有多少符合條件的子集
棋盤問題：N皇後，解數獨等等
回溯演算法的本質是縱向遍歷
回溯演算法模板為
貪心的本質是選擇每一階段的局部最優，從而達到全局最優
貪心演算法一般分為如下四步：
將問題分解為若干個子問題
找出適合的貪心策略
求解每一個子問題的最優解
將局部最優解堆疊成全局最優解
eg：擺動序列
如果連續數字之間的差嚴格地在正數和負數之間交替，則數字序列稱為擺動序列。第一個差（如果存在的話）可能是正數或負數。少於兩個元素的序列也是擺動序列。
例如， [1,7,4,9,2,5] 是一個擺動序列，因為差值 (6,-3,5,-7,3) 是正負交替出現的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是擺動序列，第一個序列是因為它的前兩個差值都是正數，第二個序列是因為它的最後一個差值為零。
給定一個整數序列，返回作為擺動序列的最長子序列的長度。 通過從原始序列中刪除一些（也可以不刪除）元素來獲得子序列，剩下的元素保持其原始順序。
示例 2:
輸入: [1,17,5,10,13,15,10,5,16,8]
輸出: 7
解釋: 這個序列包含幾個長度為 7 擺動序列，其中一個可為[1,17,10,13,10,16,8]。