search

YuezhenQin / javase

Implement Data Structures and Algorithms (Sorting, Searching, Greedy, DP) from Sketch
2 stars 1 forks source link

Greedy (贪婪): ask for maximum/minimum #46

Open YuezhenQin opened 3 months ago

YuezhenQin commented 3 months ago

A greedy algorithm refers to a way of approaching problems that makes the locally optimal decision at every step.

Let's break this definition down. First, what makes a decision "optimal"? This will depend on the problem. For example, if we are choosing some elements and the problem wants us to find the maximum sum of elements we take, then given a choice between two numbers, it is optimal to take the larger one.

Second, what makes a decision "local"? A decision is local when it considers only the available options at the current step. It is based on the information it has at the time, and doesn't consider any consequences that may happen in the future from this decision.

Most greedy problems will be asking for the maximum or minimum of something, but not always. This is a characteristic that is shared with dynamic programming, which we will learn about soon.

Another thing to note is that in many greedy problems, you will be sorting the input at the start. Again, this is because we want to greedily choose the max/min elements in many problems, and sorting the input makes this convenient.

YuezhenQin commented 3 months ago

Usually, if a problem can be solved greedily, then it is the fastest way to solve it. The hard part is figuring out if you can use greedy. The concept of "greedy" is extremely general and the main thing to practice is recognizing when it applies.