Dynamic Programming

Dynamic Programming (DP) caches overlapping subproblems to avoid recomputation.

Key Ideas

• Define a state (what does dp[i] represent?).
• Write a transition (how to compute dp[i] from earlier states).
• Choose top-down (memo) or bottom-up (tabulation).