Part VII · Dynamic Programming: Comprehensive Problem Families
46. Tree, Graph, Bitmask and Digit Dynamic Programming
7 lessons•33 topics•Intermediate / Advanced
0 of 7 lessons published
46.01Outline
Tree DP
- Include/exclude node
- Maximum independent set
- Vertex cover on tree
- Tree matching
- Count colorings
46.02Outline
Rerooting problems
- Sum of distances from each node
- Best root
- Diameter endpoints
- Rerooting memoization
46.03Outline
DAG and graph DP
- Count paths
- Longest paths
- Shortest paths with constrained resources
- SCC condensation states
46.04Outline
Bitmask DP
- State subsets
- Traveling salesman
- Assignment
- Hamiltonian path
- Minimum clique cover
- Submask transitions
46.05Outline
Profile DP
- Grid tiling masks
- Broken-profile DP
- Transfer between rows
- State compression
46.06Outline
Digit DP
- Prefix-bounded counts
- Tight flag
- Leading zeros
- Digit sum constraint
- Forbidden digits
- Automaton digit DP
46.07Outline
Probability DP
- Expected moves
- Markov chains finite-state DP
- Expected cost recurrence
- Probabilistic transitions