Dynamic Programming (DP) is a powerful algorithmic technique for solving complex problems by breaking them into simpler overlapping subproblems and storing their solutions to avoid redundant computation. It is a cornerstone of computer science used in optimization, sequence analysis, graph algorithms, and beyond.
Dynamic Programming is an algorithmic paradigm that solves a problem by dividing it into overlapping subproblems, solving each subproblem only once, and storing the results for reuse. It was formalized by Richard Bellman in the 1950s. Unlike divide-and-conquer (e.g., merge sort), DP applies specifically when subproblems overlap and share repeated computations. Classic examples include the Fibonacci sequence, the 0/1 Knapsack problem, and Longest Common Subsequence (LCS).
A problem is suitable for DP if it exhibits two properties: optimal substructure and overlapping subproblems. Optimal substructure means an optimal solution to the whole problem can be constructed from optimal solutions of its subproblems. Overlapping subproblems means the same subproblems are solved multiple times during a naive recursive approach. Both properties must be present — if subproblems don't overlap, simple recursion or divide-and-conquer is sufficient.
There are two primary DP implementation strategies: top-down (memoization) and bottom-up (tabulation). Memoization uses recursion and caches results of subproblems in a hash map or array as they are computed, solving only what is needed. Tabulation builds a table iteratively from the smallest subproblems up to the final answer, filling every cell in a defined order. Tabulation is generally more space- and cache-efficient, while memoization is often easier to derive directly from a recursive definition.
The key step is defining the state: a set of parameters that uniquely describe a subproblem (e.g., dp[i] = minimum cost to reach step i). Next, write a recurrence relation that expresses dp[state] in terms of smaller states (e.g., dp[i] = min(dp[i-1], dp[i-2]) + cost[i]). Then define base cases to anchor the recursion and determine the correct evaluation order. Finally, identify which state holds the final answer.
DP trades time for space: by storing subproblem results, it reduces exponential naive recursive complexity to polynomial in many cases. For example, naive recursive Fibonacci is O(2^n), while DP reduces it to O(n) time and O(n) space — or O(1) space with a rolling variable. The total time complexity is typically O(number of distinct states × work per state). Always analyze whether all states are reachable to avoid over-allocating memory.
A frequent mistake is defining states too broadly or too narrowly, leading to incorrect recurrences or exponential state spaces. Always verify that your recurrence is acyclic — each state must depend only on previously computed, smaller states. For large inputs, watch for integer overflow in accumulated sums and consider space optimization by keeping only the rows or values you actually need (e.g., reducing a 2D DP table to two 1D arrays). When in doubt, start with a brute-force recursive solution, identify repeated calls, then add memoization as a first DP step.
© RM Full Stack & AI Engineer · All guides · Roadmaps · Open the app