Dynamic programming

Dynamic programming solves problems by breaking them into overlapping subproblems, storing intermediate results, and combining them to obtain an optimal solution.

Bellman equation: A recursive equation that expresses an optimal value in terms of immediate outcomes and future values. It formalizes how each subproblem’s best value depends on choices and later states.
Knapsack problem: An optimization problem that selects items with given weights and values under a capacity limit. Its capacity-indexed subproblems show how dynamic programming tracks a scarce resource.
Recursion: A method of defining or solving a problem in terms of smaller instances of itself. Dynamic programming commonly begins with a recursive formulation of its subproblems.
Greedy algorithm: An algorithm that repeatedly makes a locally preferred choice without reconsidering earlier choices. Greedy methods avoid exploring full subproblem tables but require a stronger choice property.
Memoization: A technique that caches function results so repeated calls with the same inputs reuse earlier computations. It implements top-down dynamic programming by saving recursive subproblem results.
Longest common subsequence: The longest sequence appearing in the same relative order within two given sequences. A two-dimensional table combines prefix comparisons to find the optimal shared subsequence.
Principle of optimality: Bellman’s principle that an optimal policy has optimal continuation policies from states it reaches. It justifies solving each reachable future decision problem optimally on its own.
Divide-and-conquer algorithm: An algorithmic strategy that splits a problem into smaller independent subproblems and combines their solutions. Unlike dynamic programming, its subproblems typically do not overlap.
Tabulation: A technique that fills a table of subproblem results in an order that makes dependencies available. It implements bottom-up dynamic programming without recursive calls.
Edit distance: The minimum cost of transforming one string into another through permitted edit operations. Each pair of prefixes forms a subproblem linked by insertion, deletion, and substitution.

Linked from 22 pages