Algorithms For Dummies, 2nd Edition

Chapter 16

Relying on Dynamic Programming

IN THIS CHAPTER

Understanding what dynamic means when used with programming

Using memoization effectively for dynamic programming

Discovering how the knapsack problem can be useful for optimization

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.

This chapter presents dynamic programming. It explains how 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 ...