chat

详细介绍一下 贪心算法

贪心算法（Greedy Algorithm）是一种在每一步选择当前状态下局部最优解的算法策略，希望通过一系列局部最优选择得到全局最优解。

贪心算法通常比其他方法（如动态规划）简单、高效，但它并不总是适用，也无法保证在所有情况下找到最优解。

因此，使用贪心算法时需要先确认问题是否满足贪心选择的条件。

贪心算法的特点

  1. 贪心选择性质：
    • 在解决问题时，可以通过每一步的局部最优选择来构成最终的全局最优解。
    • 这一性质意味着每一步的选择不会影响后续选择，从而使得只需关注当前状态下的最优决策，而不需要回溯或全面搜索。
  2. 最优子结构：
    • 问题的最优解包含子问题的最优解，即可以通过递归或逐步的方式构建全局解。
    • 最优子结构性质是动态规划和贪心算法的共同特点，但贪心算法是基于“局部最优”，而动态规划则基于“全局最优”。
  3. 无后效性：
    • 每一个选择只依赖当前状态，不受后续状态的影响。选完一次后，无需再回头修改。

贪心算法的适用场景

贪心算法适用于满足贪心选择性质和最优子结构的问题，这些问题通常有一个特殊的结构，使得局部最优解能逐步构建成全局最优解。

常见的适用场景包括：

  • 区间问题：如区间选择问题、活动选择问题等。
  • 最小生成树：如Kruskal算法和Prim算法，用于图的最小生成树问题。
  • 最短路径问题：如Dijkstra算法，用于加权有向图的单源最短路径问题。
  • 资源分配问题：如背包问题的贪心解、任务调度等。

贪心算法的设计步骤

  1. 分析问题的最优子结构：
    • 确定问题是否能通过逐步选择局部最优解得到全局最优解。
  2. 设计贪心策略：
    • 找到一种策略，使每一步的选择都是当前状态下的最优选择。这一步通常是整个贪心算法的关键。
  3. 证明贪心策略的正确性：
    • 证明所设计的贪心策略能得到最优解，或找到反例。通常可以通过归纳法、反证法或数学推理证明。
  4. 实现算法：
    • 依据贪心策略实现算法的每一步，尽可能简化计算，避免不必要的循环或回溯。

贪心算法的经典例题

例题1：区间调度问题

题意：给定多个区间，要求选择尽量多的区间，使得它们互不重叠。

贪心策略：每次选择结束时间最早且不与已选择区间重叠的区间。

证明思路：选择结束时间最早的区间可以为后续区间留出更多时间，增加选择的可能性，从而达到最多选择。

算法步骤：

  1. 按照区间结束时间升序排序。
  2. 遍历区间，选择与上一个已选择区间不重叠的区间。

例题2：最小生成树（Kruskal算法）

题意：在一个加权无向图中，找到包含所有节点的最小生成树。

贪心策略：每次选择当前权值最小且不形成环的边。

证明思路：按照权值从小到大选择边并避免环的出现，可以保证每次选择都是局部最优，最终可以构成最小生成树。

算法步骤：

  1. 按权重对边进行排序。
  2. 用并查集维护连通性，逐步选择不形成环的边，直到构成最小生成树。

例题3：任务调度问题

题意：给定多个任务及其完成时间和收益，要求在规定时间内完成尽可能多的任务，获得最大收益。

贪心策略：优先选择收益最高的任务并分配最早的时间。

证明思路：在每一步选择收益最高的任务，分配最早的可用时间，可以保证收益最大化。

算法步骤：

  1. 按照收益对任务降序排序。
  2. 对于每个任务，找到最早的时间点完成任务，并记录收益。

贪心算法的优缺点

  • 优点：
    • 简单高效：不需要回溯或动态规划的复杂计算，通常具有较低的时间复杂度。
    • 易于实现：每一步操作清晰直接，算法逻辑相对简单。
  • 缺点：
    • 局限性：贪心算法只适用于特定类型的问题，不能保证所有问题得到全局最优解。
    • 需要验证正确性：每个问题的贪心策略需要严格证明或验证其最优性。

贪心算法与其他算法的对比

  1. 与动态规划的对比：
    • 贪心算法每步选择局部最优解，而动态规划则通过保留历史子问题的结果找到全局最优。
    • 动态规划适合有“重叠子问题”和“最优子结构”的问题，而贪心算法更适合满足“贪心选择性质”的问题。
    • 动态规划一般需要较多的空间和时间复杂度，而贪心算法通常更为高效。
  2. 与回溯法的对比：
    • 回溯法尝试所有可能的解，从中找到最优解，而贪心算法只关注局部最优，不会回溯。
    • 回溯法在很多场景下能找到全局最优解，但时间复杂度较高，而贪心算法更适合在保证局部最优的场景中。

贪心算法的总结

贪心算法在许多优化问题中是一个非常有用的策略，尤其是当问题具有某种特殊性质时（如活动选择问题、最小生成树等）。

学习和理解贪心算法的应用场景以及其局限性是掌握贪心算法的关键。

编写贪心算法的过程中，务必确保每一步的选择在当前状态下都是最优的，并且这些局部最优选择能最终汇聚成全局最优解。

贪心和动态规划区别是什么

贪心算法和动态规划都是常见的优化算法，适用于解决最优问题，但它们在解决问题的方式和适用场景上有一些关键区别：

1. 基本思路

  • 贪心算法：每一步都选择当前状态下的局部最优解，以期在最后得到全局最优解。它的核心是“贪心选择”——即每次只关注当前的最优选择，而不回溯或考虑其他路径。
  • 动态规划：将问题划分成一系列子问题，通过保存子问题的解来避免重复计算，从而得到全局最优解。动态规划的核心是“最优子结构”和“子问题重叠”——即一个问题的最优解可以由其子问题的最优解构成，并且相同子问题会被多次计算。

2. 适用问题

  • 贪心算法适用于问题的局部最优解可以带来全局最优解的情况，例如最短路径、活动选择问题等。这类问题满足“贪心选择性质”，即局部最优解必然包含在全局最优解中。
  • 动态规划适用于问题中包含多个重叠的子问题，并且整体最优解可以通过多个子问题的最优解构成的情况。经典的例子有背包问题、最短路径问题（如Floyd算法）和字符串编辑距离等。

3. 求解过程

  • 贪心算法的决策过程是“自顶向下”的，逐步推进，不需要回溯，一般时间复杂度较低，但不保证每次都能找到全局最优解。
  • 动态规划通常是“自底向上”求解，即先求解子问题，再逐层构建解决更大问题。需要保存状态、使用表格记录结果，空间复杂度较高。

4. 能否保证最优解

  • 贪心算法不一定总能得到最优解，仅在满足贪心选择性质的问题中才有效。因此，使用贪心算法需要证明其适用性。
  • 动态规划保证能找到全局最优解，因为它遍历所有可能的子问题，并利用最优子结构性质得出最优解。

举例

  • 贪心算法：如求解“找零问题”——如果面额为1、5、10、20的硬币，且贪心选择当前最大面额的硬币，可以得出最小硬币数。对于特定面额组合，贪心策略会有效。
  • 动态规划：如求解“背包问题”——需要考虑物品是否放入背包，并求解每个子集的最优解。贪心策略通常无法保证找到背包问题的全局最优解。

总结

  • 贪心算法：快速、无需回溯，适用于特定类型的最优问题，但不能普遍适用。
  • 动态规划：能求得全局最优解，适用于存在重叠子问题的复杂问题，但计算量较大。

那是不是动态规划一定能解决贪心算法的问题？

动态规划并不一定能解决所有贪心算法能解决的问题。

虽然动态规划的求解过程一般是更全面的，但由于两者的设计思路不同，动态规划并不能直接取代贪心算法来解决所有问题。

以下是一些具体原因：

1. 贪心算法的问题可能不需要动态规划的复杂性

  • 贪心算法往往用于局部最优解可以直接构成全局最优解的问题，求解过程简单明了且效率高。例如，求解最小生成树的Kruskal和Prim算法就用到了贪心策略，它们通过每次选择局部最优的边来构造最小生成树。
  • 对于这些问题，贪心算法的简单性和效率是其优势。用动态规划来解决此类问题通常会引入额外的复杂性，反而会增加时间和空间成本，而没有必要。

2. 贪心策略有特定的“贪心选择性质”

  • 贪心算法适用于“贪心选择性质”的问题，即每次做出的局部最优选择一定包含在最终的全局最优解中。动态规划虽然考虑了所有可能的子问题，但并不直接利用这种贪心性质。对于一些贪心算法适用的问题，动态规划并不能轻易找到合适的子问题分解策略。
  • 示例：求解活动选择问题（例如，最大化可以进行的活动数量）时，每次选择结束时间最早的活动是最优的。动态规划在这种情况下反而会引入不必要的复杂计算，而无法轻易得到贪心策略的局部最优路径。

3. 问题结构可能不适合动态规划

  • 动态规划适用于具有“重叠子问题”且“最优子结构”明显的场景。然而，有些贪心算法的问题虽然适合“贪心选择”，但不具备明显的重叠子问题，或者不能简单地通过子问题组合成全局最优解。这种情况下，动态规划可能难以建模并求解。
  • 示例：求解哈夫曼编码（Huffman Coding）问题时，贪心选择策略每次选取最小频率的两个符号合并。在这种情况下，动态规划并不容易构建合适的子问题模型，因此很难找到合适的动态规划方案。

4. 动态规划和贪心算法的适用场景不同

  • 贪心算法更适用于不需要保存和对比多种子解的情况，即局部最优选择不会影响后续选择。
  • 动态规划在问题解的构建过程中需要依赖其他子问题的最优解，而贪心算法只需要当前的局部最优信息。很多情况下，动态规划和贪心算法适用的场景存在差异。

总结

贪心算法和动态规划适用于不同的问题结构。

动态规划并不能完全替代贪心算法，因为贪心算法解决的问题往往不需要动态规划的复杂性，甚至有些问题的特性使得动态规划无法有效求解。

在使用贪心算法时，需要首先验证其满足贪心选择性质，而动态规划通常需要重叠子问题和最优子结构的保证，因此各有其适用的最佳场景。

贪心算法 leetcode 经典题目

在LeetCode上，有不少经典题目可以用贪心算法来解决。下面是一些较为经典的贪心算法题目，它们适用于多种常见场景，并且有助于掌握贪心算法的思路和技巧。

1. 跳跃游戏系列

  • 题目：Jump Game (跳跃游戏) - LeetCode 55
  • 题意：判断是否能从数组的起点跳跃到终点。

  • 思路：维护一个可以到达的最远位置。遍历数组时更新最远可达位置，如果最远可达位置大于等于最后一个位置，则返回 true。

  • 扩展题：Jump Game II (跳跃游戏II) - LeetCode 45
    • 题意：计算到达终点的最少跳跃次数。
    • 思路：同样维护一个最远可达位置，并在跳跃次数上做优化。每当当前跳跃范围到达时，增加跳跃次数并更新跳跃范围。

2. 分发糖果

  • 题目：Candy - LeetCode 135
  • 题意：给定一个学生的评分数组，分发最少的糖果，使得评分高的学生获得更多糖果，且每个学生至少获得一颗糖果。
  • 思路：用两次遍历（左到右和右到左）实现贪心策略，保证评分高的学生拿到更多糖果。

3. 无重叠区间

  • 题目：Non-overlapping Intervals - LeetCode 435
  • 题意：给定一些区间，删除最少数量的区间以使得剩下的区间不重叠。
  • 思路：按照区间的结束时间排序，并优先选择结束早的区间。每次选择一个不与上次选择的区间重叠的区间。

4. 用最少箭头射爆气球

  • 题目：Minimum Number of Arrows to Burst Balloons - LeetCode 452
  • 题意：每个气球有一个区间表示，问至少需要多少箭头能射爆所有气球。
  • 思路：类似无重叠区间问题，按气球结束位置排序，然后用贪心策略计算最小箭头数。

5. 划分字母区间

  • 题目：Partition Labels - LeetCode 763
  • 题意：将字符串划分为尽可能多的段，使得每个字母只出现在一个分段内。
  • 思路：计算每个字母最后出现的索引，按贪心策略从左到右遍历，划分成尽量大的片段。

6. 分配饼干

  • 题目：Assign Cookies - LeetCode 455
  • 题意：给定两个数组，一个表示每个孩子的需求，一个表示每个饼干的大小，计算可以满足的最大孩子数量。
  • 思路：将饼干和孩子的需求排序，每次用最小的饼干满足最小需求的孩子。

7. 买卖股票系列

  • 题目：Best Time to Buy and Sell Stock II - LeetCode 122
  • 题意：给定每日股票价格，允许多次交易（当天买入和卖出），求最大利润。
  • 思路：贪心策略是找到所有上升区间，将每个上升区间的收益累加，即买入谷底，卖出峰顶。

8. 会议室

  • 题目：Meeting Rooms II - LeetCode 253
  • 题意：给定一些会议的时间段，求需要的最少会议室数量。
  • 思路：先按开始时间排序，然后使用贪心策略和优先队列管理每个会议的结束时间，维护最少会议室数。

9. 零钱兑换问题

  • 题目：Coin Change II - LeetCode 518
  • 题意：给定一些面额的硬币，计算最少的硬币数量组成目标金额。
  • 思路：虽然该问题可以用动态规划解决，但在一些面额设置下，也可用贪心策略。确保面额从大到小，选择当前面额最多的硬币，逐步减少目标金额。

10. 车加油问题

  • 题目：Minimum Number of Refueling Stops - LeetCode 871
  • 题意：在一个长途旅行中，计算最少加油次数使车辆能够到达目的地。
  • 思路：用最大堆按贪心策略选择油量最多的加油站。

总结

这些经典贪心算法题目涵盖了多种场景，如区间选择、子数组操作、排序和最大/最小计算等。

熟练掌握这些题目，可以帮助理解贪心算法的局部最优解策略，以及如何证明贪心策略在特定场景下能达到全局最优解。

参考资料

https://leetcode.cn/problems/house-robber/description/?envType=problem-list-v2&envId=dynamic-programming