Dynamic Programming: Turning Brute Force Into Something That Scales

Dynamic programming (DP) is what happens when a brute-force recursive solution keeps re-solving the same subproblem, and you decide to remember the answer instead of recomputing it. Two properties make a problem a DP candidate: optimal substructure, where the best answer is built from the best answers to its subproblems, and overlapping subproblems, where the same subproblem recurs throughout a naive recursion tree.

In competitive programming, spotting these two properties quickly is often the difference between a solution that finishes in time and one that times out. The same instinct — cache what's expensive to recompute — shows up constantly in production systems, from memoized API calls to precomputed aggregation tables.

Top-down DP (memoization) starts from the original problem and recurses downward, storing each subproblem's answer the first time it's computed. It reads close to the natural recursive definition, which makes it easier to derive correctly under time pressure.

Bottom-up DP (tabulation) builds the answer iteratively from the smallest subproblems upward. It avoids recursion overhead and stack limits, and it's usually easier to optimize for memory once the recurrence is proven correct.

A handful of patterns cover most interview and contest DP problems: 0/1 and unbounded knapsack, longest increasing subsequence (including its O(n log n) form), interval DP such as matrix chain multiplication, digit DP for counting numbers with a property, and bitmask DP for small-set combinatorial problems like TSP on at most ~20 nodes.

Recognizing which pattern a new problem maps to is a skill built from repetition — the reason I keep returning to problem sets even outside of active contests.