1.貪心算法

? 貪心算法是一種在每一步選擇中都采取在當前狀態下最好或最優的選擇，從而希望全局最好或是最優的算法。

1. 特點
   • 局部最優選擇
   • 不能保證全局最優
   • 高效
2. 適用條件
   • 局部最優可以導致全局最優
   • 問題的最優解包含子問題的最優解
3. 經典問題
   • 活動選擇問題
   • 最短路徑
   • 最小生成樹

2.動態規劃

? 動態規劃是一種分治思想，通常將原問題分解為相對簡單的子問題的方式來求解復雜問題的方法。動態規劃常常適用于有重疊子問題和最優子結構性質的題.

1. 特點
   • 重疊子問題：問題可以分解成若干子問題，且子問題會重復出現
   • 問題的最優解包含子問題的最優解
   • 存儲子問題的解以避免重復計算
2. 適用條件
   • 局部最優可以導致全局最優
   • 問題的最優解包含子問題的最優解
3. 經典問題
   • 斐波那契數列
   • 背包問題
   • 最長公共子序列
   • 最短路徑問題
4. 解題步驟
   1. 確定dp數組（dp table）以及下標的含義
   2. 確定遞推公式
   3. dp數組如何初始化
   4. 確定遍歷順序
   5. 舉例推導dp數組

3.回溯

? 回溯算法是一種通過探索所有可能的候選解來找出所有解的算法。

1. 特點

   • 系統性：逐步構建候選解
   • 跳躍性：當發現部分候選解不可能得到正確解時，放棄該解（剪枝）
   • 通常用遞歸實現

2. 經典問題

   • 組合問題：N個數里面按一定規則找出k個數的集合
   • 切割問題：一個字符串按一定規則有幾種切割方式
   • 子集問題：一個N個數的集合里有多少符合條件的子集
   • 排列問題：N個數按一定規則全排列，有幾種排列方式
   • 棋盤問題：N皇后，解數獨等等

3. 代碼框架

   void backtracking(參數) {if (終止條件) {存放結果;return;}for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {處理節點;backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結果}
   }

4.三者區別