Algorithms For Dummies

Explaining Dynamic Programming

Dynamic programming is as effective as an exhaustive algorithm (thus providing 

correct solutions), yet it is often as efficient as an approximate solution (the com-

putational time of many dynamic programming algorithms is polynomial). It 

seems to work like magic because the solution you need often requires the algo-

rithm to perform the same calculations many times. By modifying the algorithm 

and making it dynamic, you can record the computation results and reuse them 

when needed. Reusing takes little time when compared to recalculating, thus the 

algorithm finishes the steps quickly. The following sections discuss what dynamic 

programming involves in more detail.