Dynamic programming

Dynamic programming is a method for solving complex problems by breaking them into simpler overlapping subproblems and reusing the solutions. It applies whenever a problem exhibits two properties: optimal substructure (an optimal solution can be assembled from optimal solutions of its parts) and overlapping subproblems (the same smaller problems are encountered repeatedly during a naive recursive solution). When subproblems do not overlap, the appropriate technique is divide and conquer instead. The method was introduced by Richard Bellman at RAND in the 1950s as a framework for sequential decision problems in operations research. Bellman later admitted choosing the name partly to disguise the mathematical nature of the work from a hostile Secretary of Defense — dynamic sounded active, and programming meant scheduling rather than writing code. There are two standard implementation styles. The top-down approach writes the natural recursive formulation and applies Memoization so each subproblem is computed only once. The bottom-up approach, called tabulation, fills a table from the smallest subproblem upward and is usually more memory-efficient and easier to parallelise. Both produce the same answers; the choice is one of code clarity and constant factors. Classic applications include shortest-path algorithms such as Bellman-Ford and Floyd-Warshall, the knapsack problem, matrix-chain multiplication, sequence alignment in bioinformatics (Needleman-Wunsch, Smith-Waterman), edit distance, optimal binary search trees, and Viterbi decoding in speech recognition and communications. Reinforcement learning inherits the Bellman equation directly, making dynamic programming a foundational tool in modern machine learning as well.