Dynamic Programming

"Those who cannot remember the past are condemned to repeat it." Dynamic Programming (DP) saves previously computed subproblem results in a lookup table, transforming exponential $O(2^n)$ recursive explosions into polynomial $O(n)$ time.

Memoization vs Tabulation

1. Memoization (Top-Down)

Natural recursive structure wrapped with a cache/hash map. Solves only required subproblems on-demand.

2. Tabulation (Bottom-Up)

Iterative array filling from base cases $DP[0], DP[1]$ upwards. Eliminates recursive stack overhead.

Quick Summary

DP is the supreme weapon for optimization problems with overlapping subproblems.
Next, we explore Graph Algorithms.