Dynamic Programming: A Gentle Intro

Dynamic programming taught from intuition: overlapping subproblems and memoization on naive Fibonacci, bottom-up tabulation with climbing stairs, then coin change as real DP and how to recognize an optimal-substructure problem when you see one.

1. Overlapping Subproblems and Memoization Naive recursive Fibonacci is exponentially slow because it solves the same subproblems over and over. Memoization stores each subproblem's answer the first time it is computed, collapsing O(2^n) work into O(n).
2. Bottom-Up Tabulation The same dynamic programming idea, flipped: instead of recursing down and caching, build the answer from the smallest cases upward with a loop and a table. Climbing stairs shows the pattern, then the rolling two-variable version trims the memory.
3. Coin Change and Spotting DP The min-coins coin-change problem, where a greedy loop gives the wrong answer and dynamic programming gives the right one. Then the two signals - optimal substructure and overlapping subproblems - that tell you a problem is DP in the first place.