Dynamic Programming

📓 Introduction: The Magic Notebook Trick

Imagine your math teacher walks up to the board and writes down: 1 + 1 + 1 + 1 + 1 = ?

You count them up on your fingers: "1, 2, 3, 4, 5." You shout out: "It's 5!" Your teacher smiles and writes down another + 1 at the very end of the line: 1 + 1 + 1 + 1 + 1 + 1 = ?

How do you find the new answer? Do you start counting from the beginning again? "1, 2, 3..."

No, of course not! That would take too long. Instead, you look at your notebook and say: "I already know the first part equals 5, so I just add 1 more to get 6!"

This is exactly what Dynamic Programming (often called DP for short) is!

Dynamic Programming is a super-smart way of solving complex problems by breaking them down into simpler, smaller questions. The magic trick is that we write down the answers to the smaller questions in a notebook (memory) so we never have to do the same math twice!

---

🧠 Recursion vs. Dynamic Programming

In the Recursion guide, we learned that a function can call itself to open smaller "nesting dolls" of a problem. But pure recursion has a huge weakness: it is extremely forgetful.

Imagine trying to calculate the 5th Fibonacci number using pure recursion. The computer ends up calculating the 2nd Fibonacci number over and over again from scratch! It does the exact same homework multiple times because it has no memory.

Dynamic Programming is Recursion with a Brain. By adding a memory table, we turn a program that would take billions of years to run into one that finishes in a fraction of a millisecond!

---

🦸 The Two Flavors of DP: Top-Down vs. Bottom-Up

When writing Dynamic Programming solutions, you can choose between two main strategies to fill your "magic notebook."

1. Memoization (Top-Down) — The "Lazy" Way 😴

• How it works: You start with the big problem you want to solve. You break it down recursively, but before doing any math, you check your notebook: "Have I solved this before?"
  • If yes: Just look up the answer and return it instantly!
  • If no: Do the calculation, write the answer in your notebook, and then return it.
• Why it's cool: It follows the natural recursive logic we already know, only adding a memory dictionary or array.

2. Tabulation (Bottom-Up) — The "Builder" Way 🧱

• How it works: You don't use recursion. Instead, you start from the very smallest, easiest questions (the base cases) and solve them first. You write them in a table (usually an array), then use those answers to build the next answers, and the next, until you reach the top!
• Why it's cool: It is often faster because it doesn't use the computer's recursion call stack, avoiding "Stack Overflow" errors.

---

✨ The Two Golden Rules of DP

You can use Dynamic Programming to solve a problem if it meets these two rules:

1. Overlapping Subproblems: You have to solve the exact same smaller questions multiple times. (Like counting 1 + 1 + 1 + 1 + 1 over and over).
2. Optimal Substructure: You can find the best answer to the big problem by combining the best answers of the smaller problems. (Like building the answer for 6 from the answer for 5).

---

🧩 Problem 1: Climbing Stairs (The DP Upgrade)

Imagine you are climbing a staircase that has n steps. You can climb either 1 step or 2 steps at a time. How many distinct ways can you climb all the way to the top?

The Strategy

• Base Case: 1 step has 1 way. 2 steps have 2 ways (1+1, or 2).
• State Relation: To reach step i, we must have come from step i-1 or step i-2. So: dp[i] = dp[i-1] + dp[i-2]

Complete Implementations (Tabulation Approach)

🕵️ Code Breakdown: Why is the code written this way?

Let's dissect the Climbing Stairs code line-by-line so we understand the engineering choices:

1. Why do we allocate an array of size n + 1? In programming, arrays are 0-indexed (meaning the first box is at position 0). If we want to find the answer for step 10 (where n = 10), we need to access dp[10]. If we allocated an array of size exactly 10, the indices would only go from 0 to 9, causing our program to crash with an "Out of Bounds" error! Making the array size n + 1 gives us indices from 0 to n so we can query our step numbers directly.
2. Why do we initialize dp[1] = 1 and dp[2] = 2? These are our Base Cases—the simple building blocks we already know the answer to.
   • If there is only 1 step, there is only 1 way to climb it (a single 1-step hop).
   • If there are 2 steps, there are exactly 2 ways: take two 1-step hops (1 + 1), or take one big 2-step hop (2). We write these starting rules in our notebook first so we can build the rest on top of them.
3. What does dp[i] = dp[i - 1] + dp[i - 2] mean? This is our State Transition Relation. Imagine you are standing on step 5. How did you get here?
   • You either jumped from step 4 (by taking a 1-step hop).
   • Or you jumped from step 3 (by taking a 2-step hop). Therefore, the total number of ways to reach step 5 is equal to (all the ways to reach step 4) + (all the ways to reach step 3). The code does exactly this for every step starting from step 3 all the way to n.

---

🧩 Problem 2: Coin Change (Making Change Smartly)

Imagine you are a cashier. You have coins of different values (like [1, 2, 5] dollars) and you need to make exactly 11 dollars using the fewest number of coins possible. How do you do it?

The Strategy

Instead of trying random combinations, we use our notebook to write down the minimum coins needed to make every single amount from $0 all the way to $11!

• Base Case: To make $0, we need exactly 0 coins (dp[0] = 0).
• State Relation: For any amount a, we check what happens if we use each coin option. For a coin of value c, the coins needed would be: 1 + dp[a - c] (the 1 coin we just chose + the best way to make the remaining amount).
• We want the absolute minimum option among all coin choices: dp[a] = min(dp[a], 1 + dp[a - coin])

Complete Implementations (Tabulation Approach)

🕵️ Code Breakdown: Why is the code written this way?

Let's unpack the logic behind the Coin Change solution:

1. Why do we initialize the array with amount + 1? Since we are looking for the minimum number of coins, we need to compare options and pick the smallest one using a min() function. If we started our array filled with 0s, then min(0, our_coin_count) would always choose 0, which is incorrect! To fix this, we fill the array with a large value representing "infinity" (in this case, amount + 1, because it's impossible to need more coins than the target amount itself unless we are using fractional coins, which we aren't). This acts as a sentinel value so any valid coin count we find will easily replace it.
2. Why is dp[0] = 0? This is our starting building block (Base Case). How many coins do you need to make exactly $0? You need exactly 0 coins.
3. Why do we have nested loops?
   • Outer Loop (for a from 1 to amount): We use a bottom-up builder strategy. We don't try to solve $11 right away. Instead, we solve the problem for $1 first, write it in our notebook, then solve for $2, then $3, all the way up to $11.
   • Inner Loop (for coin in coins): For any specific target amount a, we look at all the coin options in our pocket to see which coin gives the best (smallest) result.
4. What does dp[a] = min(dp[a], 1 + dp[a - coin]) mean? This is the core formula! Let's say we want to make $5 (a = 5) and we are checking a $2 coin (coin = 2).
   • If we choose to use the $2 coin, we have $3 left to make (5 - 2 = 3).
   • We check our notebook to see the best way to make $3 (dp[3]). Let's say the notebook says we need 2 coins to make $3.
   • So, if we use the $2 coin, the total count is 1 coin (the $2 coin we used) + 2 coins (to make the remaining $3). That's 1 + dp[3] = 3 coins in total.
   • We compare this count (3) against whatever best answer we already had written in our notebook for $5 (dp[5]), and write down the smaller of the two.

---

🚫 Common Mistakes (The DP Traps!)

Dynamic Programming can be tricky at first. Watch out for these standard bugs:

1. Off-by-One Array Allocation: If you need to calculate an answer for amount n, your DP table needs to be size n + 1. If you size it exactly to n, you will get an out-of-bounds error when trying to access dp[n]!
2. Forgetting to Initialize Sentinel Values: When looking for a minimum (like in Coin Change), you must initialize your table with a large placeholder (like infinity). If you initialize it with 0, your program will always think 0 is the minimum coins needed, and you will get the wrong answer!
3. Invalid Base Cases: If your base cases are wrong, the error will cascade through the entire table and ruin the final answer. Double check your starting points!

---

📚 Summary

• Dynamic Programming is recursion with memory.
• It works on problems with overlapping subproblems and optimal substructure.
• Memoization is top-down recursion that caches results.
• Tabulation is bottom-up iteration that fills a table.
• DP turns slow exponential $O(2^n)$ runtime into fast linear $O(n)$ or polynomial runtime!

---

🎮 Practice Problems & Website Verifications

Verify your Dynamic Programming logic by solving these interactive problems on our platform:

• Climbing Stairs — The classic introduction to 1D DP tabulation.
• Coin Change — Learn to build solutions based on choice optimization.
• House Robber — Practice making take-or-leave decisions recursively or iteratively.
• Maximum Subarray — Master Kadane's Algorithm, a beautiful variant of greedy dynamic programming.

Want to see how complex 2D Dynamic Programming works? Step through the classic Knapsack builder: