Dynamic Programming solves problems by breaking them into overlapping subproblems and storing results to avoid recomputation. The Fibonacci example illustrates both approaches: top-down memoization uses recursion with a cache, while bottom-up tabulation iteratively builds the solution. Bottom-up often achieves O(1) space when only the previous values are needed, as in House Robber and Climbing Stairs problems where the recurrence simplifies to Fibonacci-like formulas.
Classic DP problems include the 0/1 Knapsack (each item used at most once), Unbounded Knapsack (items reusable), Coin Change (minimum coins or count ways), and Longest Common Subsequence. These problems typically use 1D or 2D DP arrays with transitions based on include/exclude choices. The target sum and partition equal subset sum problems reduce cleverly to knapsack variants by transforming the problem formulation.
String-based DP problems form a substantial category. Edit Distance (Levenshtein) computes minimum insertions, deletions, and substitutions using a 2D table. The Longest Palindromic Subsequence equals the LCS of a string and its reverse. Regular Expression Matching and Wildcard Matching handle pattern matching with special characters. Interval DP applies to problems where decisions affect ranges, like Burst Balloons and Matrix Chain Multiplication. The Super Egg Drop problem inverts the DP direction, computing the maximum floors checkable with given moves and eggs. DP on DAGs and trees extends the technique to graph structures, with digit DP handling counting problems with positional constraints.