Dynamic Programming

Dynamic programming refers to a problem solving approach, in which we precompute and store simpler, similar subproblems, in order to build up the solution to a complex problem. It is similar to recursion, in which calculating the base cases allow us to inductively determine the final value. This bottom-up approach works well when the new value depends only on previously calculated values.

An important property of a problem that is being solved through dynamic programming is that it should have overlapping subproblems. This is what distinguishes DP from Divide and Conquer in which storing the simpler values aren't necessary.

To show how powerful the technique can be, here are some of the most famous problems commonly approached through Dynamic Programming:

1. Backpack Problem Given a set of treasures with known values and weights, which of them should you pick to maximize your profit whilst not damaging your backpack which has a fixed capacity?
2. Egg Dropping What is the best way to drop n eggs from an m floored building to figure out the lowest height from which the eggs when dropped cracks?
3. Longest Common Subsequence Given two sequences, which is the longest subsequence common to both of them.
4. Subset Sum Problem Given a set and a value n, is there a subset the sum of whose elements is n?
5. Fibonacci Numbers Is there a better way to compute fibonacci numbers than plain recursion?

In a contest environment dynamic programming almost always comes up (and often in a surprising way, no matter how familiar the contestant is with it).