What is dynamic programming?
What is dynamic programming?
How is it different from recursion, memoization, etc?
I have read the wikipedia article on it, but I still don't really understand it.
Answer
Dynamic programming is when you use past knowledge to make solving a future problem easier.
A good example is solving the Fibonacci sequence for n=1,000,002.
This will be a very long process, but what if I give you the results for n=1,000,000 and n=1,000,001? Suddenly the problem just became more manageable.
Dynamic programming is used a lot in string problems, such as the string edit problem. You solve a subset(s) of the problem and then use that information to solve the more difficult original problem.
With dynamic programming, you store your results in some sort of table generally. When you need the answer to a problem, you reference the table and see if you already know what it is. If not, you use the data in your table to give yourself a stepping stone towards the answer.
The Cormen Algorithms book has a great chapter about dynamic programming. AND it's free on Google Books! Check it out here.