Dynamic programming

Dynamic programming is a problem-solving technique where complex problems are broken into overlapping subproblems, solved once, and their solutions cached for reuse. Rather than repeatedly recalculating the same results, it trades memory for speed—a powerful approach when Recursion would otherwise waste computation.

The method shines when a problem exhibits optimal substructure (an optimal solution builds from optimal solutions to smaller instances) and overlapping subproblems (the same subproblem recurs many times). By storing intermediate results in a table—a process called memoization—dynamic programming avoids redundant work.

Classic examples include computing Fibonacci sequences, finding shortest paths in weighted graphs, and solving the knapsack problem in optimization. The approach fundamentally changed computer science by making previously intractable problems solvable in reasonable time.

Dynamic programming isn't a specific Algorithm but a general strategy, applicable across Combinatorics, Graph theory, and Operations research. It requires careful problem restructuring: identifying the right state variables, defining recurrence relations, and building solutions bottom-up (or top-down with memoization).

Related

Algorithm design, Greedy algorithm, Computational complexity, Memoization, Dijkstra's algorithm