Dynamic Programming Practice List
Group 1: Warmup ProblemsBasic questions to get a feel of DP 0 / 3 | |
Group 2: Linear Sequences with Constant TransitionDp 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 ProblemsDp 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-sequenceThe 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 DPThe dp sub problem is solved on every single interval (subarray) of the array. 0 / 6 | |
Group 6: Linear Sequences with non-constant TransitionDp 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 ProblemsDp 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 Teaching 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.