O'Reilly logo

Algorithms For Dummies by Luca Massaron, John Paul Mueller

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 16

Relying on Dynamic Programming

IN THIS CHAPTER

check Understanding what dynamic means when used with programming

check Using memoization effectively for dynamic programming

check Discovering how the knapsack problem can be useful for optimization

check Working with the NP-complete traveling salesman problem

Instead of using brute force, which implies trying all possible solutions to a problem, greedy algorithms provide an answer that is quick and often satisfying. In fact, a greedy algorithm can potentially solve the problem fully. Yet, greedy algorithms are also limited because they make decisions that don’t consider the consequences of their choices. Chapter 15 shows that you can’t always solve a problem using a greedy algorithm. Therefore, an algorithm may make an apparently optimal decision at a certain stage, which later appears limiting and suboptimal for achieving the best solution. A better algorithm, one that doesn’t rely on the greedy approach, can revise past decisions or anticipate that an apparently good decision is not as promising as it might seem. This is the approach that dynamic ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required