# 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 | |||
---|---|---|---|

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" |

If you prefer watching videos instead, here are some options:

Resources | |||
---|---|---|---|

Youtube | Great Introductory Errichto DP Video | ||

Youtube | Another Errichto DP video regarding coin change | ||

Youtube | Another Errichto DP video | ||

Youtube | more DP videos, but some are more related to interview questions than CP |

### Pro Tip

It's usually a good idea to write a slower solution first. For example, if the complexity required for full points is $\mathcal{O}(N)$ and you come up with a simple $\mathcal{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.

## 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

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 "easy"
problems from the knapsack module if this is your first
encounter with DP.

Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|

Gold | Easy | ## Show TagsDP | |||||||

Gold | Easy | ## Show TagsDP | |||||||

Gold | Normal | ## Show TagsDP | |||||||

Gold | Normal | ## Show TagsDP | |||||||

Gold | Easy | ## Show Tags2P, Binary Search, DP | |||||||

## Harder USACO

Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|

Gold | Hard | ## Show TagsDP | |||||||

Gold | Hard | ## Show TagsDP | |||||||

Gold | Hard | ## Show TagsDP, Floyd-Warshall, Prefix Sums | |||||||

Plat | Hard | ## Show TagsDP | |||||||

Gold | Very Hard | ## Show TagsDP | |||||||

Gold | Very Hard | ## Show TagsDP | |||||||

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!