Introduction to Dynamic Programming (DP)

Definition

Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems. It solves each subproblem only once and stores the result (usually in a table or array) to avoid re-computing it.

How it Works

Think of DP as “Recursion with a Notepad.”

1. Break it Down: Take a big problem and split it into smaller pieces.
2. Solve Once: Solve the first small piece.
3. Memoize (Write it Down): Store the answer in your “notepad” (an array or hash map).
4. Reuse: If you need that answer again later, don’t solve it again! Just look at your notepad.

Real-World Analogy

1 + 1 + 1 + 1 + 1…

• Question: What is 1+1+1+1+1?
• You: 5.
• Question: What if I add another +1 at the end?
• You: 6.
• Why was that fast? You didn’t recount the first five 1s. You remembered the previous sum (5) and just added 1. That’s Dynamic Programming.

Two Approaches

1. Top-Down (Memoization): Start with the big problem and break it down. (Recursive)
2. Bottom-Up (Tabulation): Start with the smallest subproblem and build up to the answer. (Iterative)