Dynamic Programming (DP) is about solving complex problems by breaking them into overlapping subproblems and storing their results to avoid redundant calculations.
Overlapping Subproblems
If you solve the same sub-task multiple times (like in naive Fibonacci), you're wasting time. DP identifies these overlaps and ensures each is only computed once.
Memoization vs. Tabulation
Memoization is the top-down approach that caches results of recursive calls. Tabulation is the bottom-up approach that builds a table iteratively. Both lead to the same efficiency.
The Transition Function
The core of any DP problem is finding the recurrence relation (transition) that describes how the solution to a larger problem depends on the solutions to smaller ones.