Skip to content
C Codeloom
DSA

Dynamic Programming: 8 Classic Problems with Solutions

Eight classic dynamic programming problems — Climbing Stairs, House Robber, Coin Change, LIS, Word Break, 0/1 Knapsack, Edit Distance, and LCS — each with Python solutions and DP tables.

·10 min read · By Yash Kesharwani
Intermediate 20 min read

What you'll learn

  • ✓How to identify state, transition, and base case for eight classic DP problems
  • ✓How to draw the DP table for a 1D and 2D problem
  • ✓When to use top-down memoization vs bottom-up tabulation
  • ✓Patterns for sequence DP (LIS, LCS) and choice DP (Knapsack, Coin Change)
  • ✓How to recognise these patterns in interview questions

Prerequisites

This post solves eight DP classics. For each, we identify the state, write the recurrence, draw the table when it helps, and give a clean Python solution. By the end you’ll have a mental library of patterns to draw on.

1. Climbing Stairs

Problem. You can climb 1 or 2 stairs at a time. How many distinct ways can you climb n stairs?

Examples. n = 2 → 2 ways (1+1, 2). n = 5 → 8 ways.

State. ways(i) — number of ways to reach step i.

Transition. ways(i) = ways(i-1) + ways(i-2). The last step was either a 1 (from i-1) or a 2 (from i-2).

DP table for n = 6:

i       :  0   1   2   3   4   5   6
┌───┬───┬───┬───┬───┬───┬────┐
ways(i) │ 1 │ 1 │ 2 │ 3 │ 5 │ 8 │ 13 │
└───┴───┴───┴───┴───┴───┴────┘
▲
ways(4) = ways(3) + ways(2) = 3 + 2 = 5
Climbing Stairs DP table — each cell is the sum of the previous two
def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(n - 2):
        a, b = b, a + b
    return b

print(climb_stairs(5))    # 8

2. House Robber

Problem. Given a list nums of house values, you cannot rob two adjacent houses. Return the maximum money you can rob.

Examples. [2, 7, 9, 3, 1] → 12 (rob houses 0, 2, 4: 2+9+1). [1, 2, 3, 1] → 4 (rob 0, 2: 1+3).

State. rob(i) — best loot from houses 0..i.

Transition. rob(i) = max(rob(i-1), rob(i-2) + nums[i]). Either skip this house, or rob it and add the best from i-2.

DP table for [2, 7, 9, 3, 1]:

i        :  0   1   2   3   4
nums[i]  :  2   7   9   3   1
┌───┬───┬────┬────┬────┐
rob(i)   │ 2 │ 7 │ 11 │ 11 │ 12 │
└───┴───┴────┴────┴────┘
▲          ▲
rob(2) = max(7, 2+9) = 11
rob(4) = max(11, 11+1) = 12
House Robber DP table — at each step, skip or take
def rob(nums):
    if not nums:
        return 0
    prev, curr = 0, 0
    for n in nums:
        prev, curr = curr, max(curr, prev + n)
    return curr

print(rob([2, 7, 9, 3, 1]))    # 12

3. Coin Change

Problem. Given coins of denominations coins and a target amount, return the fewest coins that sum to amount, or -1 if impossible.

Examples. coins = [1, 2, 5], amount = 11 → 3 (5+5+1). coins = [2], amount = 3 → -1.

State. f(n) — fewest coins to make amount n.

Transition. f(n) = min(f(n - c) + 1 for c in coins if c <= n). Base: f(0) = 0.

DP table for coins = [1, 2, 5], amount = 11:

n     :  0  1  2  3  4  5  6  7  8  9  10  11
┌───┬──┬──┬──┬──┬──┬──┬──┬──┬──┬───┬───┐
f(n)  │ 0 │1 │1 │2 │2 │1 │2 │2 │3 │3 │ 2 │ 3 │
└───┴──┴──┴──┴──┴──┴──┴──┴──┴──┴───┴───┘
▲
f(11) = min(f(10), f(9), f(6)) + 1 = min(2,3,2) + 1 = 3
Coin Change DP table — each cell looks back by every coin
def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for n in range(1, amount + 1):
        for c in coins:
            if c <= n and dp[n - c] + 1 < dp[n]:
                dp[n] = dp[n - c] + 1
    return dp[amount] if dp[amount] != INF else -1

print(coin_change([1, 2, 5], 11))    # 3
print(coin_change([2], 3))           # -1

4. Longest Increasing Subsequence (LIS)

Problem. Given nums, find the length of the longest strictly increasing subsequence.

Examples. [10, 9, 2, 5, 3, 7, 101, 18] → 4 ([2, 3, 7, 101]).

State. lis(i) — length of LIS ending at index i (must include nums[i]).

Transition. lis(i) = 1 + max(lis(j) for j < i if nums[j] < nums[i]), default 1.

Answer. max(lis(i) for all i).

def length_of_lis(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    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)

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

This is O(n²). There is an O(n log n) algorithm using binary search and a “patience sort” idea, but the DP version is what to know first.

5. Word Break

Problem. Given a string s and a dictionary words, can s be segmented into a space-separated sequence of dictionary words?

Examples. s = "leetcode", words = ["leet", "code"] → True. s = "applepenapple", words = ["apple", "pen"] → True. s = "catsandog", words = ["cats", "dog", "sand", "and", "cat"] → False.

State. dp[i] — can s[:i] be segmented?

Transition. dp[i] = any(dp[j] and s[j:i] in words for j < i). Base: dp[0] = True.

def word_break(s, words):
    word_set = set(words)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[len(s)]

print(word_break("leetcode", ["leet", "code"]))    # True
print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))    # False

6. 0/1 Knapsack

Problem. Given weights, values, and a capacity W, pick a subset of items (each at most once) maximising total value, subject to total weight ≤ W.

Examples. weights = [1, 3, 4, 5], values = [1, 4, 5, 7], W = 7 → 9 (items 1 and 3: 4+5, weight 3+4=7).

State. dp[i][w] — best value using items 0..i-1 with capacity w.

Transition. dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]) (skip or take).

DP table for the example above (rows = items, columns = capacity):

w=0  w=1  w=2  w=3  w=4  w=5  w=6  w=7
┌────┬────┬────┬────┬────┬────┬────┬────┐
(none)  │  0 │  0 │  0 │  0 │  0 │  0 │  0 │  0 │
+item0  │  0 │  1 │  1 │  1 │  1 │  1 │  1 │  1 │
+item1  │  0 │  1 │  1 │  4 │  5 │  5 │  5 │  5 │
+item2  │  0 │  1 │  1 │  4 │  5 │  6 │  6 │  9 │
+item3  │  0 │  1 │  1 │  4 │  5 │  7 │  8 │  9 │
└────┴────┴────┴────┴────┴────┴────┴────┘
▲
answer = 9
0/1 Knapsack DP table — items 0..i, capacity 0..7
def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i - 1][w - weights[i - 1]] + values[i - 1])
    return dp[n][W]

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

This can be compressed to a 1D table by iterating w from W down to weights[i-1].

7. Edit Distance

Problem. Given two strings s1 and s2, return the minimum number of single-character edits (insert, delete, replace) to convert s1 to s2.

Examples. "horse" → "ros" → 3. "intention" → "execution" → 5.

State. dp[i][j] — edit distance between s1[:i] and s2[:j].

Transition.

if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]
else: dp[i][j] = 1 + min(dp[i-1][j],     # delete
                        dp[i][j-1],     # insert
                        dp[i-1][j-1])   # replace

Base. dp[i][0] = i, dp[0][j] = j.

DP table for “horse” → “ros”:

""   r   o   s
┌────┬───┬───┬───┐
""    │  0 │ 1 │ 2 │ 3 │
h     │  1 │ 1 │ 2 │ 3 │
ho    │  2 │ 2 │ 1 │ 2 │
hor   │  3 │ 2 │ 2 │ 2 │
hors  │  4 │ 3 │ 3 │ 2 │
horse │  5 │ 4 │ 4 │ 3 │
└────┴───┴───┴───┘
▲
answer = 3
Edit Distance table — rows = s1 prefix, columns = s2 prefix
def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],
                                   dp[i][j - 1],
                                   dp[i - 1][j - 1])
    return dp[m][n]

print(edit_distance("horse", "ros"))           # 3
print(edit_distance("intention", "execution")) # 5

8. Longest Common Subsequence (LCS)

Problem. Given strings s1 and s2, return the length of the longest subsequence present in both.

Examples. "abcde", "ace" → 3 ("ace"). "abc", "def" → 0.

State. dp[i][j] — LCS length of s1[:i] and s2[:j].

Transition.

if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Base. dp[i][0] = dp[0][j] = 0.

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[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[m][n]

print(lcs("abcde", "ace"))    # 3
print(lcs("abc", "def"))      # 0

LCS and Edit Distance are siblings — same shape, different transition. Once you see one, the other clicks.

Try it yourself. Modify the LCS solution to return the actual subsequence, not just the length. Hint: trace back through the table from dp[m][n] — when characters match, prepend and step diagonally; otherwise step in the direction of the larger neighbour.

Patterns to take away

These eight problems split into a few recognisable shapes:

  • Linear sequence DP (Climbing Stairs, House Robber, Coin Change, Word Break) — 1D state, scan left to right.
  • Subsequence DP (LIS) — 1D state over indices, double loop.
  • Choice DP / Knapsack family (0/1 Knapsack) — 2D state, “take or skip.”
  • Two-string DP (Edit Distance, LCS) — 2D state, three-way transition.

When you see a new problem, ask: which of these shapes does it look like? You will be right surprisingly often.

Try it yourself. Try Unique Paths — given an m × n grid, how many distinct paths from top-left to bottom-right, moving only right or down? Hint: dp[i][j] = dp[i-1][j] + dp[i][j-1]. This is the Knapsack table shape with a Climbing Stairs transition.

Recap

You now have:

  • Eight worked DP problems across four pattern families
  • DP tables drawn out for the ones where they help most
  • A pattern-matching habit: recognise the shape, write the state, transition, and base
  • Clean Python solutions you can adapt

Next steps

The next two posts move to a different corner of DSA — bit manipulation. We start from the basics (AND, OR, XOR, shifts) and then apply them to clever tricks and classic interview problems.

→ Next: Bit Manipulation Basics

Questions or feedback? Email codeloomdevv@gmail.com.