Algorithms For Dummies

 Challenging Difficult Problems

results that you won’t use later. On the other hand, bottom-up approaches better 

reflect the approach that you’d take in everyday life when facing a problem (think-

ing recursively, instead, needs abstraction and training before application). Both 

top-down and bottom-up approaches aren’t all that easy to understand at times. 

That’s because using dynamic programming transforms the way you solve prob-

lems, as detailed in these steps:

1. 

Create a working solution using brute-force or recursion. The solution works 

but it takes a long time or won’t finish at all.

2. 

Store the results of subproblems to speed your computations and reach a 

solution in a reasonable time.

3. 

Change the way you approach the problem and gain even more speed.

4. 

Redefine the problem approach, in a less intuitive but more efficient way to 

obtain the greatest advantage from dynamic programming.

Transforming algorithms using dynamic programming to make them work effi-

ciently makes them harder to understand. In fact, you might look at the solutions 

and  think  they  work  by  magic.  Becoming  proficient  in  dynamic  programming 

requires repeated observations of existing solutions and some practical exercise. 

This proficiency is worth the effort, however, because dynamic programming can 

help you solve problems for which you have to systematically compare or compute 

solutions.

Dynamic programming is especially known for helping solve (or at least make less 

time demanding) combinatorial optimization problems, which are problems that 

require obtaining combinations of input elements as a solution. Examples of such 

problems solved by dynamic programming are the traveling salesman and the 

knapsack problems, described later in the chapter.