Dynamic Programming Intro

Dynamic Programming Intro

Dynamic programming, or DP, solves a hard problem by breaking it into smaller subproblems, solving each once, and combining their answers. It applies when a problem has two properties.

The two ingredients

• Overlapping subproblems: the same smaller problems recur many times, so caching their answers saves enormous work.
• Optimal substructure: an optimal solution to the whole is built from optimal solutions to its parts.

The Fibonacci sequence shows both. A naive recursion recomputes the same values exponentially, but storing each computed value makes it linear.

Two styles

• Top down starts from the original problem and recurses, caching results as it goes. This is memoization.
• Bottom up fills a table from the smallest subproblems upward until the full answer appears. This is tabulation.

Designing a DP solution means defining a clear state that captures everything needed and a transition that relates a state to smaller states.

Key idea

When subproblems overlap and combine optimally, solving each once and reusing it turns exponential work into polynomial work.