Course contentsShow
← Computer Science
Lesson 913 of 2,87222. Dynamic ProgrammingFree lesson

What is Dynamic Programming?

Define dynamic programming as an optimization technique that solves problems by breaking them into overlapping subproblems.

What is Dynamic Programming?

You'll learn: What dynamic programming is and how it solves complex problems by reusing solutions to overlapping subproblems.

The Core Idea

Dynamic programming (DP) is an optimization technique that transforms complex problems into simpler ones by breaking them down into overlapping subproblems. The key insight? If you're solving the same smaller problem multiple times, solve it once, store the answer, and reuse it whenever needed.

Think of it like solving a jigsaw puzzle. Instead of randomly trying pieces, you group similar sections together (sky, edges, patterns). When you need a "blue sky piece," you look in your organized blue pile—you don't re-search the entire box. Dynamic programming does this with computations.

What Makes It "Dynamic"?

The term sounds fancy, but "dynamic" simply means we make decisions at each step based on previously computed results. We build solutions bottom-up (solving smallest subproblems first) or top-down (solving as needed and remembering results).

The critical difference from divide-and-conquer? Overlapping subproblems. In divide-and-conquer, subproblems are independent. In DP, subproblems repeat, so we store and reuse their solutions—this is called memoization.

When to Use Dynamic Programming

Look for these clues:

  • You can break the problem into smaller versions of itself
  • Those smaller problems appear multiple times
  • The problem asks for optimization (minimum, maximum, count all ways)

Classic example: calculating Fibonacci numbers. Computing fib(5) requires fib(4) and fib(3). But fib(4) also needs fib(3)—we'd recalculate it unnecessarily without DP!

Key Takeaway: Dynamic programming solves problems efficiently by identifying overlapping subproblems, solving each once, and storing results for reuse—transforming exponential problems into polynomial ones.