What Is Dynamic Programming? A Simple Explanation With Solved Examples in Python and JavaScript

Dynamic programming sounds advanced but the idea is small: do not solve the same problem twice. Once you can spot repeated work and name the state, most DP questions follow the same five steps.

When dynamic programming applies

• Overlapping subproblems. The same smaller problem is needed again and again. Plain recursive Fibonacci recalculates fib(3) many times.
• Optimal substructure. The best answer to the whole problem is built from the best answers to its parts, as in the shortest route through a map.

If subproblems do not overlap, you are doing divide and conquer, such as merge sort. If a locally best choice is always safe, a greedy algorithm may be enough.

Memoization vs tabulation

Example 1: Fibonacci, naive vs memo vs table

The plain version makes 2,692,537 calls to compute fib(30). The cached version computes each value once, 31 in total, and the table version is a simple loop.

from functools import lru_cache

calls = 0
def fib_naive(n):
    global calls
    calls += 1
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)

@lru_cache(maxsize=None)
def fib_memo(n):                         # top-down: recursion + a cache
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)

def fib_table(n):                        # bottom-up: fill a table in order
    if n < 2:
        return n
    table = [0, 1]
    for i in range(2, n + 1):
        table.append(table[i - 1] + table[i - 2])
    return table[n]

print(fib_naive(30), calls)
print(fib_memo(30), fib_memo.cache_info().misses)
print(fib_table(30))

Output:

832040 2692537
832040 31
832040

Example 2: Climbing stairs (1D DP)

You can climb 1 or 2 steps at a time. The ways to reach step n equal the ways to reach n - 1 plus n - 2. Only the last two values matter, so two variables are enough.

function climbStairs(n) {
  let prev = 1, curr = 1;              // ways to reach step 0 and step 1
  for (let step = 2; step <= n; step++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

console.log(climbStairs(5), climbStairs(10));

Output: 8 89

Example 3: Coin change (fewest coins)

best[a] is the fewest coins that make amount a. For each amount, try every coin and keep the smallest result.

def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount               # best[a] = fewest coins that make a
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and best[a - coin] + 1 < best[a]:
                best[a] = best[a - coin] + 1
    return best[amount] if best[amount] != INF else -1

print(min_coins([1, 5, 10, 25], 63), min_coins([2], 3))

Output: 6 -1. Sixty-three needs 25 + 25 + 10 + 1 + 1 + 1, and an amount of 3 cannot be made from only 2s.

Example 4: 0/1 knapsack

Choose items, each at most once, to maximise value within a weight limit. Looping the capacity backwards makes sure each item is counted once.

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

print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))

Output: 9, from the items of weight 3 and 4.

Example 5: Longest common subsequence (2D DP)

dp[i][j] is the LCS length of the first i characters of a and the first j characters of b. A match extends the diagonal; otherwise take the better of dropping one character.

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"))

Output: 4

How to solve a DP problem, step by step

1. Check for repeated work. Draw the recursion tree for a small input and look for identical subproblems.
2. Define the state. What is the smallest set of values that fully describes a subproblem, such as an index and a remaining capacity?
3. Write the recurrence. Express a state using smaller states.
4. Set the base cases and decide the fill order, or add a cache to the recursion.
5. Read off the answer, then reduce space if only the last row or the last few values are needed.

Types of DP problems

Common mistakes

• Jumping to a table before writing the recurrence.
• A state that is too big, or missing a variable, so the answers are wrong.
• Using the wrong fill order, so a cell is read before it is computed.
• Counting an item twice in knapsack by looping the capacity forwards.
• Not memoizing at all and calling plain recursion "DP".

Practice problems, in order

1. Climbing Stairs
2. House Robber
3. Coin Change
4. Unique Paths
5. Longest Increasing Subsequence
6. Longest Common Subsequence
7. Partition Equal Subset Sum
8. Edit Distance
9. Word Break

Start from recursion, then read the Masai guide to dynamic programming 101 for more worked problems.

Frequently asked questions

Learn this with mentors

Programmes for builders and engineers with admissions open: live classes, mentors and project work.

Leap AI Residency CohortMasai

8 weeks→

Advanced Certification in AI & MLVishlesan i-Hub, IIT Patna

8 months→

AI & ML Certification ProgramE&ICT Academy, IIT Roorkee

6 months→