二十二、贪心算法

访问 www.coding-time.cn 阅读原文动画效果，体验更佳。

1.贪心算法

在计算机科学中，贪心算法（Greedy Algorithm）和动态规划（Dynamic Programming）是两种常见的算法设计策略。虽然它们都属于算法设计领域，但在解决问题时采用了不同的思路和方法。

1）贪心算法

贪心算法是一种简单而直观的算法策略，它在每一步选择中都采取当前状态下最优的选择，以期望得到全局最优解。贪心算法的核心思想是每次都做出局部最优的选择，希望通过局部最优解的组合来达到全局最优解。

贪心算法的特点包括：

• 贪心选择性质：每次选择局部最优解，不考虑全局最优解。
  
• 无后效性：当前的选择不会影响以后的选择。
  
• 子问题最优性：通过局部最优解来求解整体最优解。
  

贪心算法通常适用于满足贪心选择性质和无后效性的问题，而不是所有问题都适合使用贪心算法。因为贪心算法往往忽略了问题的整体结构，可能无法得到全局最优解。

2）动态规划

动态规划是一种将复杂问题分解成简单子问题并进行逐步求解的策略。它将问题划分为若干个子问题，并保存子问题的解，以便在需要时进行查找和复用。动态规划的核心思想是通过记忆化存储中间结果，避免重复计算，以提高效率。

动态规划的特点包括：

• 最优子结构：问题的最优解包含了子问题的最优解。
  
• 重叠子问题：问题可以被分解为多个重叠的子问题。
  
• 状态转移方程：通过定义递推关系来计算问题的解。
  

动态规划通常适用于满足最优子结构和重叠子问题性质的问题，它能够通过保存中间结果来避免重复计算，从而提高算法的效率。

3）区别与选择

贪心算法和动态规划在算法设计策略上存在明显的区别。贪心算法在每个步骤都选择局部最优解，希望通过局部最优解的组合达到全局最优解。它通常比较简单且高效，但不能保证得到全局最优解。

相反，动态规划通过将问题分解为子问题，并保存子问题的解，以便在需要时进行查找和复用。它能够得到全局最优解，但相对而言更复杂且计算开销较大。

选择使用贪心算法还是动态规划取决于问题的特性。如果问题满足贪心选择性质和无后效性，且局部最优解能够导致全局最优解，那么贪心算法是一个不错的选择。但如果问题具有最优子结构和重叠子问题性质，并且问题规模较大，那么动态规划可能更适合。

4）伪代码框架

以下是贪心算法和动态规划的伪代码框架示例，用于展示两种算法的基本结构和思路：

贪心算法伪代码框架

function greedyAlgorithm(problem) {
  initialize solution;
  while (solution is not complete) {
    make a greedy choice;
    update solution;
  }
  return solution;
}

带你读《图解算法小抄》二十二、贪心算法（2）https://developer.aliyun.com/article/1347852?groupCode=tech_library