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.