常见算法思想及其特点

1. 分治法（Divide and Conquer）

• 思想：将复杂问题分解为若干个规模较小的相同子问题，递归求解，最后合并子问题的解得到原问题的解。
• 特点：
  • 适用于可分解为子问题且子问题之间相互独立的场景
  • 常用于排序（如归并排序、快速排序）、大整数乘法等

2. 动态规划（Dynamic Programming）

• 思想：将原问题分解为重叠的子问题，通过保存子问题的解避免重复计算，通常采用自底向上的方式求解。
• 特点：
  • 适用于有重叠子问题和最优子结构性质的问题
  • 常用于背包问题、最长公共子序列、斐波那契数列等

3. 贪心算法（Greedy Algorithm）

• 思想：每一步都选择当前状态下最优的选择（局部最优），希望通过一系列局部最优达到全局最优。
• 特点：
  • 适用于具有贪心选择性质和最优子结构的问题
  • 常用于最小生成树、哈夫曼编码、活动选择等

4. 回溯法（Backtracking）

• 思想：通过搜索所有可能的解，遇到不满足条件的情况时回退到上一步，尝试其他可能性。
• 特点：
  • 适用于需要枚举所有解或部分解的问题
  • 常用于八皇后问题、数独、全排列、组合等