Algorithms For Dummies

 

   

  PART 5 

 Challenging Difficult Problems

Discovering the Best Dynamic Recipes

Even dynamic programming has limitations. The biggest limitation of all relates 

to its main strength: If you keep track of too many partial solutions to improve 

running time, you may run out of memory. You may have too many partial solu-

tions in store because the problem is complex, or simply because the order you use 

to produce partial solutions is not an optimal one and too many of the solutions 

don’t fit the problem requirements.

The order used to solve subproblems is something you must track. The order you 

choose should make sense for the efficient progression of the algorithm (you solve 

something that you’re going to reuse immediately) because the trick is in smart 

reuse of previously built building blocks. Therefore, using memoization may not 

provide enough benefit. Rearranging your problems in the right order can improve 

the results. You can learn how to correctly order your subproblems by learning 

directly from the best dynamic programming recipes available: knapsack, travel-

ing salesman, and approximate string search, as described in the sections that 

follow.