Dynamic Programming
Master DP patterns from basic to advanced optimization techniques
Master DP patterns from basic to advanced optimization techniques
Sections
Articles
Dynamic Programming Overview
Dynamic Programming (DP) Overview 1. Summary / TL;DR DP solves problems by breaking them into …
Knapsack Variants
Knapsack Variants Summary / TL;DR The Knapsack family of problems involves selecting items with …
LIS and Variants
Longest Increasing Subsequence (LIS) and Variants Summary / TL;DR LIS is a fundamental DP problem …
Tree DP and Subtree Problems
Tree DP and Subtree Problems Summary / TL;DR Tree DP leverages the hierarchical structure of trees …
Bitmask Dynamic Programming
Bitmask DP Summary / TL;DR Bitmask DP uses binary numbers to represent subsets, enabling efficient …
Digit Dynamic Programming
Digit DP Summary / TL;DR Digit DP solves problems of the form: “Count numbers in range [L, R] …
Dynamic Programming Optimizations
DP Optimization Techniques 1. Summary of Optimization Techniques Technique Reduces From Reduces To …
Convex Hull Trick and Li Chao Tree
Convex Hull Trick (CHT) & Li Chao Tree 1. Overview Convex Hull Trick Optimizes DP of the form: …
Sum Over Subsets DP and Bitmask DP
Sum Over Subsets (SOS) DP & Bitmask DP 1. Overview Sum Over Subsets (SOS) DP Computes for each …
Interval DP
Interval DP 📚 Summary Interval DP solves problems by considering all possible intervals [i, j] and …
String DP
String DP 📚 Summary String DP problems involve comparing, transforming, or matching strings. Common …
DP on DAGs / Topological DP
DP on DAGs / Topological DP 1. Overview Core Concept Any DP problem can be viewed as finding paths …
Partition DP (Splitting Arrays/Strings)
Partition DP 1. Overview Core Concept Partition DP deals with problems where we need to split an …
Counting DP & Combinatorics DP
Counting DP & Combinatorics DP 1. Overview Core Concept Counting DP deals with problems asking …
Probability & Expected Value DP
Probability & Expected Value DP 1. Overview Core Concept Probability DP deals with problems …
DP with Last Element / Lookback States
DP with Last Element / Lookback States 1. Overview Core Concept Many DP problems require tracking …
DP Solution Reconstruction & Path Recovery
DP Solution Reconstruction & Path Recovery 1. Overview Core Concept DP finds optimal values, but …
Meet in the Middle (Alternative to DP)
Meet in the Middle 1. Overview Core Concept Meet in the Middle (MITM) is a technique that reduces …
Advanced DP Optimizations
Advanced DP Optimizations 1. Overview This document covers advanced optimization techniques beyond …
Scheduling and Resource Allocation DP
Scheduling and Resource Allocation DP 1. Overview This document covers DP approaches for: Job/Task …
Constrained Path DP
Constrained Path DP 1. Overview This document covers DP approaches for path problems with additional …
Space Optimization and Rolling Arrays
Space Optimization and Rolling Arrays 1. Overview This document covers techniques to reduce space …