Dynamic Programming

Definitions

1. An optimization technique that solves problems by breaking them into overlapping subproblems and storing their solutions (memoization/tabulation) to avoid redundant computation. Applies when a problem has optimal substructure and overlapping subproblems. Classic examples: Fibonacci, knapsack, longest common subsequence, edit distance. The bane of coding interviews.

   In plain English: Solving complex problems by breaking them into smaller pieces, solving each piece once, and reusing the answers.

   Example: "The naive recursive solution is O(2^n), but with dynamic programming and memoization it becomes O(n) — each subproblem is solved only once."

Related Terms

• Cache
• Data Structure
• Horn Clause
• Profile
• Tail Call
• Type System
• Vectorization
• Dijkstra's Algorithm
• Greedy Algorithm
• Two Pointers