贪心，回溯，动态规划

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.三者区别