Dynamic Programming

Introductions to the Dynamic Programming (DP) could be found here:

• http://en.wikipedia.org/wiki/Dynamic_programming
• http://20bits.com/articles/introduction-to-dynamic-programming/

Main characteristics of DP are:

• overlappling subproblems
• optimal substructure

To solve DP problem we need to do next steps:

• define what we are calculating;
• define recursion formula;
• define boundary condition;
• define calculation order.

DP problems are often used in Programming Contests

• http://codeforces.com/blog/entry/325