So you want to learn Dynamic Programming? Trust me, it sounds way scarier than it actually is. At its core, DP is just a fancy way of saying "solve a big problem by breaking it into smaller pieces and remembering what you already figured out."
Think of it like this — imagine you are climbing a staircase and someone asks how many ways you can reach step 10. You could try every possible path, but that takes forever. Instead, you figure out how many ways to reach step 1, then step 2, then step 3, and build up from there. That is DP in a nutshell.
Overlapping Subproblems
The first key property of a DP problem is overlapping subproblems. This means the same smaller problems keep popping up again and again. Without DP, you would solve them over and over like a broken record. With DP, you solve each one once and store the result so you never repeat work.
Take the Fibonacci sequence — to compute fib(5), you need fib(4) and fib(3). To compute fib(4), you need fib(3) and fib(2). Notice how fib(3) shows up twice? That is an overlapping subproblem. Without caching, the naive recursive approach recalculates the same values exponentially.
Optimal Substructure
The second property is optimal substructure. This just means the optimal solution to the big problem can be built from the optimal solutions of its smaller parts.
If you know the shortest path from A to B passes through C, then the shortest path from A to C must also be optimal. Otherwise, you could swap in a better path from A to C and get a better overall route. The same logic applies to tons of real-world problems — shortest routes, cheapest combinations, best resource allocation.
When to Use DP
You reach for DP when a problem has both overlapping subproblems and optimal substructure. Classic examples include computing Fibonacci numbers, finding shortest paths in weighted graphs, and the knapsack problem.
The trick is recognizing the pattern. If a problem feels like "try everything and pick the best" but the subproblems repeat, DP is your friend. If there are no overlapping subproblems, a greedy algorithm might be simpler. If there is no optimal substructure, DP probably will not help.