Dynamic Programming Practice List

Group 1: Warmup Problems

Basic questions to get a feel of DP

0 / 3

Group 2: Linear Sequences with Constant Transition

Dp solution requires us to solve the sub problem on every prefix of the array. The definition of a prefix of an array is a subarray from 0 to i for some i.

0 / 5

Group 3: Grid Problems

Dp table will have the same dimensions as grid. The dp solution will involve solving the sub problem on a bunch of subgrids.

0 / 6

Group 4: Dual-sequence

The problem asks about calculating some value related to two sequences. Dp[i][j] will store the answer to the sub problem solved on prefix of sequence 1 with length i, and prefix on sequence 2 with length j.

0 / 6

Group 5: Interval DP

The dp sub problem is solved on every single interval (subarray) of the array.

0 / 6

Group 6: Linear Sequences with non-constant Transition

Dp problem is solved on every prefix of the array just like group 2. However, transitions may not be simple and require a linear amount of options from indices j < i.

0 / 5

Group 7: Knapsack Problems

Dp state is similar to the classical knapsack problem.

0 / 9

Group 8: Topological Sort on Graphs (advanced, optional)

Solve dp on all subgraphs that are connected to each node

0 / 3

Group 9: DP on Trees (advanced, optional)

Solve dp problem on all subtrees.

0 / 2

Additional Problems:

Miscellaneous problems that do not strictly fall into above patterns.

0 / 4

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.