EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
Data Structures & Algorithms

Dynamic Programming

The focus here is less on memorizing formulas and more on seeing what information must survive from one decision to the next.

11 published notes
4 planned topics
7 advanced or expert notes
basic starting level
Back to DSA Competitive Programming
Category Overview

Dynamic Programming

State design, transitions, and the optimizations that make large DP feasible.

Raw TeX

Overview

Dynamic programming is easier to revise when each note is centered on state design and transition shape instead of one famous problem. That is the organizing principle here.

Reading Strategy

For each topic I want to answer:

  • what the state means,

  • why the transition is complete,

  • what lets the state count stay under control,

  • which optimization becomes legal once the recurrence has the right monotonicity or convexity.

Difficulty Bands

How this branch is distributed

The labels are not cosmetic. They are there to signal the amount of prerequisite structure and implementation fragility you should expect before opening the note.

basic: 1 intermediate: 3 advanced: 7 expert: 0
1 basic
basic

These are the shortest on-ramp notes in this category and the ones most likely to be usable immediately in contest practice.

Knapsack

3 intermediate
intermediate

These notes assume the base routine is already familiar and focus on the first real structural upgrades.

Bitmask DP, Digit DP, Tree DP

7 advanced
advanced

These are the notes where proofs, reductions, or implementation details become the main bottleneck.

Monotone Queue Optimization, Divide and Conquer DP Optimization, Knuth Optimization, Convex Hull Trick, SOS DP, Rerooting DP, Aliens Trick / Lagrangian Relaxation

Published notes

What is already written

These are the finished note pages in this category, each with rendered TeX, C++ code, references, and practice suggestions.

01
basic

Knapsack

The standard capacity-based DP pattern, with the loop directions and state choices that distinguish 0/1 from unbounded use.

dynamic programming capacity DP / state transitions
02
intermediate

Bitmask DP

Dynamic programming over subsets when the state is a small visited set, partition, or compatibility frontier.

dynamic programming bitmasks / subset state
03
intermediate

Digit DP

A position-by-position DP over the decimal expansion of an upper bound, with tight and leading-zero states.

digit dp counting / memoization
04
intermediate

Tree DP

Exploit the parent-child structure of trees so each state only has to summarize one rooted subtree at a time.

dynamic programming trees / subtree states
05
advanced

Monotone Queue Optimization

Speed up DP transitions over a sliding range by keeping only the best candidates in a deque.

dynamic programming deque / optimization
06
advanced

Divide and Conquer DP Optimization

Speed up row-by-row transition minimization when the optimal split point moves monotonically.

DP optimization monotonicity / partition DP
07
advanced

Knuth Optimization

Speed up interval DP from O(n^3) to O(n^2) when the optimal split points move monotonically.

interval dp optimization / monotonicity
08
advanced

Convex Hull Trick

A deque-based lower hull for DP recurrences with monotone slopes and monotone queries.

dp optimization lines / geometry
09
advanced

SOS DP

Transform subset-based values so every mask can aggregate information from all of its submasks or supermasks efficiently.

bitmasks subset transform / DP optimization
010
advanced

Rerooting DP

Compute a tree answer for every possible root by combining one downward DP pass with one upward transfer pass.

trees all roots / DP transfer
011
advanced

Aliens Trick / Lagrangian Relaxation

Replace a hard limit on the number of chosen groups with a penalty and binary search that penalty.

dp optimization lagrangian / parametric search
Study Order

Recommended order to read this branch

The default order follows each note's dependency weight: early notes establish primitives, later notes reuse them or assume the same invariants without re-explaining them.

01
basic

Knapsack

The standard capacity-based DP pattern, with the loop directions and state choices that distinguish 0/1 from unbounded use.

dynamic programming capacity DP / state transitions
02
intermediate

Bitmask DP

Dynamic programming over subsets when the state is a small visited set, partition, or compatibility frontier.

dynamic programming bitmasks / subset state
03
intermediate

Digit DP

A position-by-position DP over the decimal expansion of an upper bound, with tight and leading-zero states.

digit dp counting / memoization
04
intermediate

Tree DP

Exploit the parent-child structure of trees so each state only has to summarize one rooted subtree at a time.

dynamic programming trees / subtree states
05
advanced

Monotone Queue Optimization

Speed up DP transitions over a sliding range by keeping only the best candidates in a deque.

dynamic programming deque / optimization
06
advanced

Divide and Conquer DP Optimization

Speed up row-by-row transition minimization when the optimal split point moves monotonically.

DP optimization monotonicity / partition DP
07
advanced

Knuth Optimization

Speed up interval DP from O(n^3) to O(n^2) when the optimal split points move monotonically.

interval dp optimization / monotonicity
08
advanced

Convex Hull Trick

A deque-based lower hull for DP recurrences with monotone slopes and monotone queries.

dp optimization lines / geometry
09
advanced

SOS DP

Transform subset-based values so every mask can aggregate information from all of its submasks or supermasks efficiently.

bitmasks subset transform / DP optimization
010
advanced

Rerooting DP

Compute a tree answer for every possible root by combining one downward DP pass with one upward transfer pass.

trees all roots / DP transfer
011
advanced

Aliens Trick / Lagrangian Relaxation

Replace a hard limit on the number of chosen groups with a penalty and binary search that penalty.

dp optimization lagrangian / parametric search
Planned topics

Next topics in this branch

These are still intentionally shown as planned or outline topics rather than shallow filler. The branch should feel incomplete in honest places instead of fake-complete everywhere.

Classical DP planned Interval DP planned Subset convolution outline Slope trick outline
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
Category TeX sourcecompetitive_programming/dsa/dynamic-programming/index.tex