Dynamic Programming

In Turkish: Dinamik Programlama

Updated September 30, 20263 min read

In short

Dynamic programming is a technique for solving problems by breaking them into overlapping subproblems and storing each answer so none is solved twice.

What is dynamic programming?

Dynamic programming (DP) is a method for solving a problem by combining the answers to smaller versions of the same problem. It applies when two conditions hold: the subproblems overlap, meaning the same smaller problems come up again and again, and the problem has optimal substructure, meaning the best overall answer can be built from the best answers to its subproblems. DP solves each distinct subproblem once, saves the result, and reuses it.

There are two common styles. Top-down DP writes a normal recursive solution and adds memoization, a cache that stores each result the first time it is computed. Bottom-up DP, also called tabulation, fills a table starting from the smallest subproblems and works upward to the final answer, without any recursion. For example, a naive recursive Fibonacci function takes exponential time because it recomputes the same values over and over, while either DP version computes the nth number in O(n) time.

An everyday analogy: if someone asks you to add up 1 + 1 + 1 + 1 + 1, you count to five; if they then add one more 1, you don't recount, you just add one to the five you remembered. DP solves classic problems such as the fewest coins that make a given amount, the longest common subsequence behind diff tools, the edit distance used by spell checkers, and the knapsack problem of packing the most value into limited space.

The name is misleading: it has nothing to do with dynamic typing, and Richard Bellman, who developed the method in the 1950s, chose the word dynamic partly because it sounded impressive. DP is often confused with divide and conquer, as used in merge sort, which also splits a problem into subproblems, but those subproblems don't overlap, so there is nothing to reuse. It also differs from a greedy algorithm, which commits to the locally best choice at each step and can miss the best answer, as when making 6 from coins of 1, 3, and 4: greedy picks 4 + 1 + 1, while DP finds 3 + 3.

Key takeaways

DP works when a problem has overlapping subproblems and optimal substructure.
Each distinct subproblem is solved once, and its result is stored for reuse.
Top-down DP uses recursion with memoization; bottom-up DP fills a table from the smallest cases.
It can turn exponential-time solutions into polynomial-time ones, such as O(n) for Fibonacci numbers.
Unlike divide and conquer, DP relies on subproblems that repeat.

Example

Fewest coins with bottom-up dynamic programmingpython

def min_coins(coins, amount):
    # best[a] = fewest coins that add up to a; start every amount as "impossible"
    best = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                # Reuse the stored answer for the smaller amount a - coin
                best[a] = min(best[a], best[a - coin] + 1)
    return best[amount] if best[amount] != float("inf") else -1

# O(amount * len(coins)) time instead of exponential recursion
print(min_coins([1, 3, 4], 6))  # 2 (3 + 3); greedy would use 3 coins (4 + 1 + 1)

Readers ask

What is the difference between dynamic programming and memoization?

Memoization is a caching technique that stores a function's result for each input so repeated calls are instant. Dynamic programming is the broader strategy of solving overlapping subproblems once, and memoization is one way to implement it, called top-down DP; the other is bottom-up tabulation.

How do I know if a problem needs dynamic programming?

Look for a problem that asks for an optimal value or a count, such as the minimum cost or the number of ways, and whose naive recursive solution recomputes the same inputs many times. If the answer for an input can be built from the answers for smaller inputs, DP is likely a good fit.

Why is it called dynamic programming?

Richard Bellman coined the name in the 1950s. Programming referred to planning and filling in tables, not writing code, and he chose dynamic partly because it sounded impressive to the officials funding his research.