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.
|CPH||Great introduction that covers most classical problems. Mentions memoization.|
|TC||great for all skill levels|
|CPC||examples with nonclassical problems|
|CP2||describes many ways to solve example problem, additional classical examples|
|HR||also covers many classical problems|
|PAPS||starts with DAGs, which are covered in "Topological Sort"|
This section is not complete.
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.
Some of these problems will be mentioned in the next few modules.
Easier USACO problems that don't require many optimizations or complex states.
Note - Ordering of DP Modules
Can be very difficult.