Incrementally construct the solution by optimizing some intermediate goal. When the solution is constructed completely, it will meet our global goal. This will require the question to have some special property to guarantee the correctness of the algorithms.
This set of algorithms highly depend on the actual question. Check the book for examples.
- Coin problem
- Question: Form a target sum of money by using minimal number of coins
- Property: If a coin can be constructed by a set of other coins, then in the final solution, there won’t appear such a set. Otherwise, we can substitute this set of coins with just one coin. For example, if we have coin 2 and 1. Then we won’t have two 1 coins in the answer, but only one 2 coin.
- Schedule task by time
- Question: Schedule as many as task (same importance) without conflict of time.
- Property: Always prioritize task that can finish early. If we schedule a late task, the current number of scheduled tasks won’t change, but it will leave a stricter requirement for the rest tasks.
- Huffman coding
- Question: encode letter (with different importance) into binary format
- Property: Incrementally construct the binary encoding tree. The deeper node will be less important. This guaranteed the total depth of all nodes weighted by their importance will be the smallest.