Greedy algorithm

greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage.

Following this strategy, we can get solutions to a variaty of problems, not necessarily the best solution.

We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage, and may reconsider the previous stage’s algorithmic path to solution.

贪心算法在很多场合都非常有效,最少它可以帮助你写出第一个工作的版本,然后从这里开始在探索更好的解决方案(比如动态规划等等)。