# Dynamic Programming

These posts show how to solve problems with dynamic programming step-by-step.

Each post follows a plan:

- build brute force recursive solution
- get surprised how slow it is and figure out why
- improve solution with memoization
- convert to “true” dynamic-programming bottom-up solution

I assume that you already know what dynamic programming is; here are few links:

- Dynamic Programming @ Wikipedia
- There is a good tutorial @topcoder
- And very nice video explanation problem-by-problem here

Still, many people look for “better” way to approach DP problems. This is what these posts are about.

### Some theory

Basically, DP is an opportunity to solve a problem of two characteristics: overlapping subproblems and optimal substructure. With this properties in mind we can exchange memory-to-time: run faster with greater memory use.

http://en.wikipedia.org/wiki/Overlapping_subproblems

http://en.wikipedia.org/wiki/Optimal_substructure

To keep definition short:

Overlapping subproblems: your solution keeps solving same sub-problems on and on.

Optimal substructure: on each step your solution is based on optimal solutions of already solved subproblems.

Top-down approach: you solve bigger problem, by calling the same logic on smaller chunks of input - this is recursive solution.

Memoization: save results of already calculated calls to smaller subproblems and reuse these results instead of recalculating the same numbers on and on.

Bottom-up approach: small problems are solved first, and then combined to more generic ones, until we get to the goal.