Algorithms For Dummies

  Relying on Dynamic Programming 

     299

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

Relying on Dynamic 

Programming

I

nstead of using brute force, which implies trying all possible solutions to a 

problem, greedy algorithms provide an answer that is quick and often satisfy-

ing. In fact, a greedy algorithm can potentially solve the problem fully. Yet, 

greedy algorithms are also limited because they make decisions that don’t con-

sider 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 appar-

ently good decision is not as promising as it might seem. This is the approach that 

dynamic programming takes.

Dynamic programming is an algorithm approach devised in the 1950s by Richard 

Ernest Bellman (an applied mathematician also known for other discoveries in the 

field of mathematics and algorithms, you can read more at 

https://en.wikipedia.

org/wiki/Richard_E._Bellman

) that tests more solutions than a corresponding 

greedy approach. Testing more solutions provides the ability to rethink and pon-

der the consequences of decisions. Dynamic programming avoids performing 

Chapter 

16

---

300

 

   

  PART 5