When a Program Recognizes a Repeat Problem
Some problems contain smaller questions that recur. A program that calculates a number in a sequence, for example, may need the same earlier values again and again. Solving each occurrence from scratch wastes time. Dynamic programming avoids that repeat work by saving answers and looking them up when they are needed again.
Two Ways to Reuse an Answer
One approach, called memoization, starts with the requested result and works downward. The program checks whether it has already solved a smaller question; if so, it returns the saved answer. If not, it solves the question, stores the result, and continues. This is especially useful when a problem has many possible subproblems but a particular run needs only some of them.
Another approach builds answers upward: solve the smallest cases first, then use them to calculate larger ones. Either way, the key is that a larger problem can be assembled from smaller answers, and those smaller answers can be reused.
The Tradeoff: Memory for Less Recalculation
Saving results takes space in memory, so dynamic programming trades storage for reduced computation. It helps when the same subproblems appear repeatedly; if they do not, keeping a record may add overhead without saving much work. The practical change is simple but powerful: instead of making a computer rediscover an answer every time it is needed, the program can retrieve it in a lookup.
