{ }SolveLog
⌕
Home / Patterns / Dynamic Programming
48 worked problems

Dynamic Programming

Carry the best answer so far, build up. Brute force repeats the same state, and the future depends on a compact summary of earlier choices.

Recognition signal

When should you think of Dynamic Programming?

Brute force repeats the same state, and the future depends on a compact summary of earlier choices.

Core invariant

What must stay true?

Each DP state stores the best or total answer for one precisely defined subproblem.

Practice in a deliberate order

Starter

Build the template

  1. #70 Climbing StairsEasy
  2. #746 Min Cost Climbing StairsEasy
Core

Recognize variations

  1. #62 Unique PathsMedium
  2. #63 Unique Paths IIMedium
  3. #64 Minimum Path SumMedium
  4. #91 Decode WaysMedium
  5. #97 Interleaving StringMedium
  6. #120 TriangleMedium
Stretch

Combine ideas under pressure

  1. #10 Regular Expression MatchingHard
  2. #44 Wildcard MatchingHard
  3. #72 Edit DistanceHard
  4. #115 Distinct SubsequencesHard

What to learn in this cluster

  1. 01One-dimensional recurrence
  2. 02Grid and subsequence DP
  3. 03Interval, stock, and partition DP

All Dynamic Programming problems

48 of 48 walkthroughs
Continue the cluster

Related patterns and study guides

Recursion & Backtracking →Greedy →Graphs →
Language choicePython vs C++ vs Java: which language should you use for DSA?Coding habitsHow to code effectively: a repeatable workflow from idea to solutionDebuggingHow to debug algorithm solutions without guessing