Dynamic Programming
/daɪˈnæm.ɪk ˈproʊ.ɡræm.ɪŋ/ · Noun · Development · Origin: 1953
Definitions
An algorithm design technique that solves complex problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the results to avoid redundant computation. Applicable when a problem has optimal substructure and overlapping subproblems.
In plain English: Instead of solving the same sub-problem over and over, solve it once, remember the answer, and reuse it. It turns impossibly slow algorithms into fast ones.
Example: "The brute-force solution was O(2^n), but once I added memoization it became a clean DP solution in O(n²)."
Origin Story
The optimization technique with a deliberately misleading name
Richard Bellman invented **dynamic programming** at RAND Corporation in the 1950s. The name was intentionally vague -- Bellman chose 'dynamic' because it sounded impressive and 'programming' referred to planning (as in military scheduling), not computer code.
Bellman later admitted he picked the name partly to hide his work from a Secretary of Defense who was hostile to mathematical research. 'Dynamic' was a word that 'no congressman could object to.' The actual technique is about solving problems by breaking them into overlapping subproblems and caching results.
Dynamic programming is the backbone of countless algorithms: shortest paths (Dijkstra, Floyd-Warshall), sequence alignment (bioinformatics), text justification, and the infamous knapsack problem. It's also the most feared topic in coding interviews, despite being conceptually simple -- the difficulty is recognizing when to apply it.
Coined by: Richard Bellman
Context: RAND Corporation, 1950s
Fun fact: Bellman's autobiography reveals the full political story: RAND's funding came from the Air Force, and the Secretary of Defense 'had a pathological fear of the word research.' So Bellman camouflaged mathematical research with a buzzwordy name. It worked -- dynamic programming became one of the most important techniques in computer science.