Dynamic programming (algorithmic method for optimization and decomposition)

Key principles

Two properties make a problem suitable for dynamic programming. First, optimal substructure: an optimal solution to the whole problem can be constructed from optimal solutions to its parts. Second, overlapping subproblems: the same small problems recur many times. When both hold, dynamic programming avoids redundant work by recording intermediate results.

Techniques and patterns

There are two common implementation strategies. Memoization stores results of function calls (top-down) while tabulation fills a table iteratively (bottom-up). Typical patterns include:

• 1D or 2D arrays for sequences and grids (e.g., longest increasing subsequence, edit distance).
• Knapsack and resource-allocation forms where capacity/state is a dimension.
• Tree and graph DP where states are nodes with ancestor/descendant relations.
• Divide-and-conquer combined with memoization for complex state spaces.

Examples and intuition

A simple illustration is computing Fibonacci numbers: naive recursion repeats many calls, but memoizing previously computed values reduces the cost dramatically. In optimisation, problems such as shortest paths, sequence alignment and various packing or scheduling tasks use dynamic programming to explore many possibilities efficiently by representing choices as states and transitions.

History and development

The term "dynamic programming" was introduced in the mid-20th century by Richard Bellman while working on problems in control theory. Bellman formalised the idea that optimal decisions satisfy a recursive relationship: the best overall decision can be framed in terms of best decisions for subsequent states. His work created a theoretical foundation still used in control, operations research and reinforcement learning.

Applications, complexity and distinctions

Dynamic programming appears across algorithms (shortest-path and edit-distance algorithms), computational biology (sequence alignment), economics (dynamic optimisation and policy evaluation), and machine learning (value iteration). The practical cost depends on the number of distinct states and the cost to compute transitions; designing a compact state representation is often the main challenge. Dynamic programming differs from greedy methods (which make locally optimal choices) and from pure divide-and-conquer (which yields independent subproblems). For further study see resources in Bellman's work and introductions from control theory texts (control theory).

For accessible overviews and algorithmic examples consult standard algorithm texts and tutorials in computer science and applied mathematics (mathematics).