Dynamic Programming 101 | Types, Examples, and Use-Cases

Dynamic programming solves a problem by storing the answers to overlapping subproblems so each is computed once. See when to use it, top-down vs bottom-up with Python and C++ code, a coin change walkthrough and the classic interview problems.

An illustration of Dynamic Programming

Dynamic programming is one of the finest ways to solve a class of problems with sub-problems. Did that sound difficult to understand? Dive in to learn all about it with clear concepts and examples.

Dynamic programming (often abbreviated as DP) is a powerful method for solving complex algorithmic problems by breaking them down into smaller, overlapping subproblems. Instead of re-calculating solutions from scratch, the results of these subproblems are calculated once and saved, a core concept known as memoization or tabulation.

If you are learning dynamic programming for beginners, abstract definitions can feel overwhelming. Let's look at a practical, real-world example to see how dynamic programming works in action.

Imagine planning a multi-city cross-country road trip. You want to find the absolute shortest route from your starting location to your final destination, passing through several intermediate stopovers.

Here is how a dynamic programming approach solves this route selection problem:

Identify the overlapping subproblems: The overall journey consists of smaller legs between intermediate cities. Rather than recalculating every possible full-length route across the entire map, you break the trip down into point-to-point sub-routes.

Solve and store intermediate calculations: Using a navigation system, you calculate the shortest distance between intermediate stops (e.g., City A to City B) and store that distance in a table for future lookup.

Combine subproblem solutions into an optimal path: When determining the best overall route, you retrieve the previously saved shortest legs rather than recalculating them. Combining these optimal sub-solutions gives you the most efficient full journey without redundant work.

This step-by-step approach breaking down complex problems, solving each sub-part once, storing the intermediate outputs, and reassembling them forms the foundation of dynamic programming in technical interviews and software engineering.

What is Dynamic Programming

Dynamic Programming (DP) is an algorithmic optimization technique used to solve complex algorithmic problems by breaking them down into simpler, overlapping subproblems. Developed by the mathematician Richard Bellman in the 1950s, DP operates on a fundamental principle: never solve the same subproblem twice.

By calculating each subproblem once and storing its output in memory using memoization (top-down) or tabulation (bottom-up), dynamic programming removes the repeated work. For Fibonacci, that takes the running time from exponential, O(2^n), down to linear, O(n).

Think of dynamic programming as recursion with a memory bank. Instead of recalculating identical recursive paths over and over, DP saves time by trading a small amount of memory space to instantly look up previously computed sub-solutions.

When to use Dynamic Programming?

Use dynamic programming when a problem has both of these properties:

  • Overlapping subproblems. The same smaller problem comes up again and again. A quick test: draw the recursion tree and look for repeated nodes. In the Fibonacci tree later in this post, F(8) appears several times.
  • Optimal substructure. The best answer to the whole problem can be built from the best answers to its parts. The shortest route from A to C through B is the shortest route from A to B plus the shortest route from B to C. Graph algorithms such as Bellman-Ford and Floyd-Warshall rely on this idea (see the graph data structure guide).

The problem statement often gives hints. Look for words such as "minimum", "maximum", "longest", "fewest" or "number of ways", applied to an array, a string, a grid or a set of items with a limit (a capacity or a target amount). If the brute-force solution tries every choice and takes exponential time, ask whether the same states keep repeating.

Not every recursive problem needs DP. This table shows where each technique fits:

TechniqueWhat the subproblems look likeUse it when
Plain recursionMay repeat, and nothing is savedThe subproblems never repeat, as in tree traversal
Divide and conquerIndependent, so they do not repeat (merge sort, binary search)Splitting the input into parts is enough
Dynamic programmingThey overlap; each is solved once and savedYou need a minimum, a maximum or a count, and the same states keep returning
GreedyNever revisitedA proof shows the locally best choice is always safe (activity selection)

Greedy can fail where DP works. Take coins of 1, 3 and 4 and a target of 6. Greedy picks 4 + 1 + 1, which is three coins. The best answer is 3 + 3, two coins, and DP finds it.

Practical Application: The Fibonacci Sequence

To really get a grip on dynamic programming, let's explore a classic example: The Fibonacci sequence.

It is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1.

Fibonacci Series: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34…and so on.

Mathematically, we could write each term using the formula:

F(n) = F(n-1) + F(n-2),

With the base values F(0) = 0, and F(1) = 1. And we’ll follow the above relationship to calculate the other numbers. Students who find such recursive formulas tricky to compute manually can use a Math Solver to work through each step and verify the output before implementing it in code. For example, F(6) is the sum of F(4) and F(5), which is equal to 8.

Let’s look at the diagram for better understanding.

Recursion tree for F(10): F(10) splits into F(9) and F(8), and the same values such as F(8), F(7) and F(6) appear several times further down

Suppose we’ve to calculate F(10). Going by the formula, F(10) should be the sum of F(8) and F(9). Similarly, F(9) would also be the sum of the subproblems F(7) and F(8). As you can see, F(8) is an overlapping subproblem here.

In the above example, if we calculate the F(8) in the right subtree, then it would result in an increased usage of resources and reduce the overall performance.

The better solution would be to store the results of the already computed subproblems in an array. First, we’ll solve F(6) and F(7) which will give us the solution to F(8) and we’ll store that solution in an array and so on. Now when we calculate F(9), we already have the solutions to F(7) and F(8) stored in an array and we can just reuse them. F(10) can be solved using the solutions of F(8) and F(9), both of which are already stored in an array.

Similarly, at each iteration we store the solutions so we don’t have to solve them again and again. This is the main attribute of dynamic programming.

If you try to compute this sequence with a straightforward recursive function, you'll end up doing a lot of unnecessary work. (Want to understand recursion from scratch?)

Here's a simple Python implementation using DP to calculate a Fibonacci sequence:

def fibonacci(n):
    # Create an array of size (n+1) to store the computed values
    dp = [0, 1] + [0] * (n - 1)

    for i in range(2, n + 1):
        # Compute the ith Fibonacci number
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

print(fibonacci(10))  # Outputs: 55

How much work does plain recursion repeat?

Count the calls. This is the plain recursive function from the formula, with a counter added:

calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10), calls)   # 55 177

Computing F(10) takes 177 calls for only 11 distinct values. The gap widens fast:

nF(n)Calls made by plain recursionValues DP computes
105517711
206,76521,89121
30832,0402,692,53731
40102,334,155331,160,28141

The call count is exactly 2 × F(n + 1) - 1, so it grows by about 1.6 times with every step. DP computes each of the n + 1 values once, which is why the running time drops from exponential to linear.

Step-by-Step Approach to DP

Most DP problems can be solved with the same five steps. Let us apply them to coin change: given coin values and a target amount, find the fewest coins that add up to the amount, or -1 if that is not possible.

  1. Spot the pattern. "Fewest" asks for an optimum, and every coin you pick leaves a smaller amount to solve, which different choices can reach. That points to DP.
  2. Define the state. Let dp[a] be the fewest coins needed to make the amount a.
  3. Write the recurrence. To make a, try every coin c that fits and keep the best: dp[a] = 1 + min(dp[a - c]) over all coins c <= a.
  4. Set the base case and the order. dp[0] = 0. Fill the table from amount 1 up to the target (bottom-up), or recurse from the target with a cache (top-down).
  5. Read the answer. It is dp[amount]. If that amount was never reached, return -1.

The solution in Python and in C++:

def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount                  # dp[0] = 0, the rest unknown
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1

print(coin_change([1, 3, 4], 6))   # 2  (3 + 3)
print(coin_change([2], 3))         # -1 (impossible)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int coinChange(const vector<int>& coins, int amount) {
    const int INF = amount + 1;                 // larger than any real answer
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[amount] == INF ? -1 : dp[amount];
}

int main() {
    cout << coinChange({1, 3, 4}, 6) << "\n";   // 2
    cout << coinChange({2}, 3) << "\n";         // -1
}

The cost of a DP solution is the number of states times the work per state. Here there are amount + 1 states and each one tries every coin, so the time is O(amount × number of coins) and the space is O(amount).

Common DP mistakes

  • Using a mutable default such as memo={} in a Python function signature. The dictionary is shared by every call, which can return stale answers when the inputs change (a different coin list, say). Pass None and create it inside, or use functools.lru_cache.
  • Wrong base cases. In Fibonacci, F(0) is 0, so if n <= 2: return 1 gets F(0) wrong.
  • Filling a table in the wrong order, so a cell reads a value that has not been computed yet.
  • Leaving a variable out of the state. If the answer depends on both the item index and the remaining capacity, the memo key needs both.

Types of Dynamic Programming

Dynamic programming is divided into two main approaches: top-down (memoization) and bottom-up (tabulation). Both of these methods help in solving complex problems more efficiently by storing and reusing solutions of overlapping subproblems, but they differ in the way they go about it.

Let's dive into these two approaches:

Top-Down DP (Memoization)

In the top-down approach, also known as memoization, we start with the original problem and break it into subproblems, like starting at the root of a tree and working down to the leaves. The function is written recursively. Before it computes anything, it checks a cache, which is a dictionary (a hash map) or an array. If the answer is there, it returns it. If not, it computes the answer, stores it and returns it.

Top-down only solves the subproblems the answer actually needs, and the code usually mirrors the recursive definition, so it is quick to write and easy to check. The cost is the call stack: deep recursion uses more memory, and in Python a depth beyond the default limit of about 1,000 raises a RecursionError.

Let's revisit the Fibonacci sequence example:

def fibonacci(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:                          # base cases: F(0) = 0, F(1) = 1
        return n
    if n in memo:                      # already solved: reuse it
        return memo[n]
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))   # 55

Here, memo is a dictionary that stores the previously computed numbers. Before we compute a new Fibonacci number, we first check if it is already in memo. If it is, we return the stored value. If it is not, we compute it, store it in memo and return it. Python's functools.lru_cache decorator does the same bookkeeping for you, as shown in the recursion guide.

Bottom-Up DP (Tabulation)

The bottom-up approach, also known as tabulation, goes the other way. You solve the smallest subproblems first and fill a table, so that by the time you reach the problem at hand, every value it needs is already in the table. That is where the name "tabulation" comes from.

The Fibonacci code earlier in this post is already bottom-up: it fills dp[0], dp[1], dp[2] and so on. There is no recursion, so there is no call stack to overflow and less overhead per step. The time complexity is the same as top-down, O(n) for Fibonacci. The saving is in overhead and often in memory, because you can keep only the values you still need. Fibonacci needs just the last two:

def fibonacci(n):
    if n < 2:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr   # keep only the last two values
    return curr

print(fibonacci(10))   # 55

The catch is that you must know the right order to fill the table, so each cell's inputs are ready before you reach it.

Which approach to choose?

Both top-down and bottom-up dynamic programming can be useful, and your choice depends on the problem at hand and the requirements of your program.

Memoization (top-down)Tabulation (bottom-up)
DirectionFrom the original problem down to the base casesFrom the base cases up to the answer
Written asRecursion plus a cacheLoops plus a table
SolvesOnly the subproblems the answer needsEvery subproblem in the table
Time (Fibonacci)O(n)O(n)
Space (Fibonacci)O(n): the cache plus the call stackO(n) for a table, or O(1) with two variables
Watch out forDeep recursion (a RecursionError in Python)Getting the fill order right

The top-down approach is often easier to write because it follows the natural logic of the problem. The bottom-up approach avoids recursion, but it needs a clearer picture of the order in which to build the answer. A common way to work is to write the recursion first, add the cache, and rewrite it as a loop only if depth or speed becomes a problem.

Top Dynamic Programming Patterns for Technical Interviews

Mastering dynamic programming for beginners becomes manageable when you focus on core patterns rather than memorizing individual solutions:

Dynamic programming examples at a glance

Every classic problem is a choice of state and recurrence. Here are eight, with their costs:

ProblemStateRecurrenceTime / space
Fibonaccidp[i] = F(i)dp[i-1] + dp[i-2]O(n) / O(1)
Climbing stairs (1 or 2 steps)dp[i] = ways to reach step idp[i-1] + dp[i-2]O(n) / O(1)
House robberdp[i] = best loot from the first i housesmax(dp[i-1], dp[i-2] + money[i])O(n) / O(1)
Coin change (fewest coins)dp[a] = fewest coins for amount a1 + min(dp[a - c])O(amount × coins) / O(amount)
0/1 knapsackdp[w] = best value with capacity wmax(dp[w], dp[w - wt] + val)O(items × capacity) / O(capacity)
Longest common subsequencedp[i][j] = LCS of the first i and first j charactersOn a match dp[i-1][j-1] + 1, else the larger of dp[i-1][j] and dp[i][j-1]O(m × n) / O(m × n)
Longest increasing subsequencedp[i] = longest one ending at i1 + max(dp[j]) for j < i with a[j] < a[i]O(n²) / O(n)
Edit distancedp[i][j] = edits to turn the first i characters of A into the first j of BOn a match dp[i-1][j-1], else 1 + the smallest of insert, delete, replaceO(m × n) / O(m × n)

The longest increasing subsequence can be brought down to O(n log n) with binary search.

1. 0/1 Knapsack Pattern

In this one-dimensional version, dp[w] is the best value for capacity w, and looping the capacity backwards makes sure each item is used at most once. It runs in O(items × capacity) time and O(capacity) space.

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)                   # dp[w] = best value with capacity w
    for wt, val in zip(weights, values):
        for w in range(capacity, wt - 1, -1):   # backwards: each item is used once
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[capacity]

print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))   # 9  (the items of weight 3 and 4)

2. Longest Common Subsequence (LCS)

Here dp[i][j] holds the LCS length of the first i characters of a and the first j characters of b. The table has m × n cells, so the time and space are both O(m × n).

def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[len(a)][len(b)]

print(lcs("ABCBDAB", "BDCABA"))   # 4  (for example "BCBA")

3. Longest Increasing Subsequence (LIS)

This is the simple O(n²) version. Each dp[i] looks back at every earlier element that is smaller.

def lis(nums):
    dp = [1] * len(nums)                # dp[i] = longest increasing subsequence ending at i
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))   # 4  (2, 3, 7, 101)

Common Beginner Interview Questions

  • Climbing Stairs (LeetCode 70): Path counting using a Fibonacci pattern.
  • Coin Change (LeetCode 322): Unbounded Knapsack variant for coin minimization.
  • House Robber (LeetCode 198): Decision-making with non-adjacent constraints.

Final Thoughts

Dynamic programming turns a daunting problem into a series of small ones, and the method is the same every time: define the state, write the recurrence, set the base case, choose an order, read the answer. It takes practice to spot overlapping subproblems and to pick the right state, so work through problems one pattern at a time instead of memorising solutions.

A sensible practice order is Fibonacci and climbing stairs, then house robber and coin change, then knapsack, then the two-string problems such as LCS and edit distance. If the recursion underneath still feels shaky, start with the recursion guide, and keep the 7-step approach to coding problems handy for interviews.

Cheers and Happy Coding!

FAQs on Dynamic Programming

When should I use Dynamic Programming?

Use DP when a problem has overlapping subproblems and optimal substructure: the same smaller problems repeat, and the best overall answer is built from the best answers to the parts. Typical signs are "minimum", "maximum", "longest" or "number of ways" on sequences, grids or sets of items.

Are there different types of Dynamic Programming?

Yes, there are two ways to implement it: top-down (memoization, which is recursion plus a cache) and bottom-up (tabulation, which fills a table with loops). Both give the same answer, usually with the same time complexity. The choice depends on clarity, recursion depth and memory.

What is the difference between recursion and dynamic programming?

Recursion is a way of writing a function that calls itself. Dynamic programming is a strategy that stores the answers to subproblems so none is solved twice. Plain recursion repeats work on overlapping subproblems, memoization fixes that, and tabulation does the same job with loops and no recursion.

Is memoization top-down or bottom-up?

Memoization is a top-down approach. It starts with the main problem, breaks it down recursively and caches the results. Tabulation is the bottom-up approach, which solves the smallest subproblems first using loops.

What is the time complexity of dynamic programming?

It is the number of distinct states times the work done per state. Fibonacci has n states with constant work each, so it takes O(n). Coin change has one state per amount and tries every coin, so it takes O(amount × coins). Plain recursion on the same problems is exponential.

What are the best strategies to learn dynamic programming for beginners?

Start by drawing recursion trees on paper to spot repeated nodes. Then practise one pattern at a time: Fibonacci and climbing stairs, house robber, coin change, knapsack, then LCS and edit distance. For each, write the state and the recurrence in words before you code.


Learn more:

The Art of Debugging: Mastering the Bug Hunt, One Error at a Time

Introduction to Object-Oriented Programming

How Software is Developed? A Step-By-Step Guide

Array vs Linked List [When to use What]

7-Step Approach to Solve Any Coding Problem

×

Our Courses

Practice-Based Learning Tracks, Supercharged By A.I.