PrevNext
Very Frequent
 0/8

Introduction to DP

Authors: Michael Cao, Benjamin Qi

Speeding up naive recursive solutions with memoization.

Dynamic Programming (DP) is an important algorithmic technique in Competitive Programming from the gold division to competitions like the International Olympiad of Informatics. By breaking down the full task into sub-problems, DP avoids the redundant computations of brute force solutions.

Although it is not too difficult to grasp the general ideas behind DP, the technique can be used in a diverse range of problems and is a must-know idea for competitors in the USACO Gold division.

General Resources

Resources
CPHGreat introduction that covers most classical problems. Mentions memoization.
TCgreat for all skill levels
CPCexamples with nonclassical problems
CP2describes many ways to solve example problem, additional classical examples
HRalso covers many classical problems
PAPSstarts with DAGs, which are covered in "Topological Sort"

Pro Tip

It's usually a good idea to write a slower solution first. For example, if the complexity required for full points is O(N)O(N) and you come up with a simple O(N2)O(N^2) solution, then you should definitely type that up first and earn some partial credit. Afterwards, you can rewrite parts of your slow solution until it is of the desired complexity. The slow solution might also serve as something to stress test against.

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

this list is pretty long, should have a good reason for including each of these

Classical Problems

The next few modules provide examples of some classical problems, or Dynamic Programming problems which are well known. However, classical doesn't necessarily mean common. Since so many competitors know about these problems, problemsetters rarely set direct applications of them.

Problemsets

Resources
CSESYou should know how to do all of these once you're finished with the DP section. Editorials are available here.
ACSome tasks are beyond the scope of Gold.

Some of these problems will be mentioned in the next few modules.

Introductory USACO

Easier USACO problems that don't require many optimizations or complex states.

Note - Ordering of DP Modules

You are not expected to complete all of the problems below before starting the other DP modules. In particular, we recommend that you begin with the knapsack module if this is your first encounter with DP.

StatusSourceProblem NameDifficultyTagsSolution
GoldEasy
Show Tags

DP

External Sol
GoldEasy
Show Tags

DP

External Sol
GoldEasy
Show Tags

DP

External Sol
GoldEasy
Show Tags

DP

External Sol

Harder USACO

Can be very difficult.

StatusSourceProblem NameDifficultyTagsSolution
GoldNormal
Show Tags

DP, Brute Force

External Sol
GoldNormal
Show Tags

DP

External Sol
PlatHardExternal Sol
GoldHard
Show Tags

DP

External Sol

Module Progress:

Give Us Feedback on Introduction to DP!

PrevNext