Dynamic Programming Demystified: A Step-by-Step Framework for Any DP Problem

Dynamic programming (DP) has a reputation for being impossible to learn. Students spend weeks on it, feel like they understand it, then blank out in interviews. The reason: they're memorising solutions instead of learning the process.

This article gives you a 4-step framework that works for any DP problem. By the end, you'll understand the reasoning behind every DP solution — not just the answers.

---

Why DP Feels Hard (and Why It Doesn't Have To)

DP is not a single technique. It's a problem-solving approach that applies when two conditions are met:

1. Overlapping subproblems: The same smaller problem is solved multiple times in a naive recursive solution
2. Optimal substructure: The optimal solution to the big problem can be built from optimal solutions to smaller problems

When both conditions hold, DP turns an exponential brute-force solution into a polynomial one.

The hard part isn't the code. It's recognising the right subproblem to define.

---

The 4-Step Framework

Step 1: Define the subproblem

Ask: "What is the smallest version of this problem that's still meaningful?"

Write it as a function definition: "dp[i] = ..."

This is the hardest step and the most important. Get this right and the rest follows.

Step 2: Write the recurrence

Ask: "How can I compute dp[i] from previously computed values?"

This is the transition equation. It expresses the current state in terms of previous states.

Step 3: Identify base cases

Ask: "What are the smallest inputs where I know the answer without any computation?"

Step 4: Decide direction (top-down or bottom-up)

• Top-down (memoisation): Write the recursion naturally, cache results
• Bottom-up (tabulation): Fill a table iteratively from base cases up

---

Worked Example 1: Climbing Stairs

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

Step 1 — Define subproblem: dp[i] = number of ways to reach stair i

Step 2 — Recurrence: To reach stair i, you came from stair i-1 (one step) or stair i-2 (two steps). So: dp[i] = dp[i-1] + dp[i-2]

Step 3 — Base cases: dp[1] = 1 (only one way: one step) dp[2] = 2 (two ways: 1+1 or 2)

Step 4 — Bottom-up:

def climb_stairs(n):
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

Space-optimised (you only need the last two values):

def climb_stairs(n):
    if n <= 2:
        return n
    
    prev2, prev1 = 1, 2
    
    for _ in range(3, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    
    return prev1

Time: O(n) · Space: O(1)

---

Worked Example 2: Coin Change (Minimise Coins)

Given coins of different denominations and a total amount, find the minimum number of coins to make that amount. Return -1 if impossible.

Step 1 — Define subproblem: dp[i] = minimum number of coins to make amount i

Step 2 — Recurrence: For each coin value c, if c <= i, then: dp[i] = min(dp[i], dp[i - c] + 1)

In English: "the minimum coins for amount i equals the minimum coins for amount (i - c) plus one more coin of value c."

Step 3 — Base cases: dp[0] = 0 (zero coins needed for amount 0) dp[i] = infinity initially (meaning "not yet reachable")

Step 4 — Bottom-up:

def coin_change(coins, amount):
    # initialise all to infinity (unreachable)
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base case
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

Trace through coins=[1,2,5], amount=6:

• dp[0]=0, dp[1]=1, dp[2]=1, dp[3]=2, dp[4]=2, dp[5]=1, dp[6]=2 ✓

Time: O(amount × coins) · Space: O(amount)

---

Worked Example 3: Longest Common Subsequence

Given strings text1 and text2, return the length of their longest common subsequence.

This is a 2D DP problem — the subproblem needs two indices.

Step 1 — Define subproblem: dp[i][j] = length of LCS of text1[0..i-1] and text2[0..j-1]

Step 2 — Recurrence:

If text1[i-1] == text2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1      # characters match: extend LCS by 1

Else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # skip one character from either string

Step 3 — Base cases: dp[i][0] = 0 for all i (empty text2 → LCS is 0) dp[0][j] = 0 for all j (empty text1 → LCS is 0)

Step 4 — Bottom-up:

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

Trace text1="abcde", text2="ace": The answer is 3 (the subsequence "ace").

Time: O(m × n) · Space: O(m × n)

---

Top-Down vs Bottom-Up: When to Use Each

Both approaches compute the same results. The choice is mostly preference.

Top-down (memoisation) — start with recursion, add cache:

def coin_change_memo(coins, amount):
    memo = {}
    
    def dp(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        if remaining in memo:
            return memo[remaining]
        
        min_coins = float('inf')
        for coin in coins:
            result = dp(remaining - coin)
            min_coins = min(min_coins, result + 1)
        
        memo[remaining] = min_coins
        return min_coins
    
    result = dp(amount)
    return result if result != float('inf') else -1

Bottom-up (tabulation) — build up from base cases:

Advantages:

• No recursion overhead (no stack overflow risk)
• Often easier to space-optimise
• Usually slightly faster in practice

Top-down advantages:

• More natural to write (just add @functools.lru_cache to recursion)
• Only computes states you actually need

In interviews: Start with the approach you're more comfortable with. If asked to optimise, switch to iterative.

---

The Most Common DP Patterns

1. Linear DP (1D array)

Subproblem depends on a few previous states.

Examples: Climbing Stairs, House Robber, Fibonacci

# House Robber — can't rob adjacent houses
def rob(nums):
    if len(nums) == 1:
        return nums[0]
    
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    
    return dp[-1]

2. Grid DP (2D array)

Two sequences or a 2D grid.

Examples: LCS, Edit Distance, Unique Paths

3. Knapsack DP

Choosing items with weights/values under a capacity constraint.

# 0/1 Knapsack
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Don't take item i
            dp[i][w] = dp[i-1][w]
            
            # Take item i (if it fits)
            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][capacity]

4. String DP

Operations on one or two strings.

Examples: Edit Distance, Palindromic Substrings, Word Break

---

The Most Common Mistake

Students see the word "maximum" or "minimum" in a problem and immediately think DP. But DP is only correct when you have overlapping subproblems. Many max/min problems are solved with greedy algorithms (Jump Game, Meeting Rooms) which are faster.

How to know if it's DP vs Greedy:

• If a locally optimal choice at each step always leads to the global optimum → Greedy
• If you need to consider all possible choices and pick the best → DP

When in doubt, start with recursion and see if subproblems repeat. If they do, add memoisation.

---

Practice Progression

Build your DP skills in this order:

1. Fibonacci / Climbing Stairs — understand the idea
2. House Robber — apply linear DP with a choice
3. Coin Change — unbounded knapsack
4. Longest Common Subsequence — 2D DP
5. Edit Distance — 2D string DP
6. Longest Increasing Subsequence — LIS with O(n log n) optimisation
7. 0/1 Knapsack — classic capacity DP
8. Word Break — string DP with a dictionary

Jump straight in: Filter the Practice section by "Dynamic Programming" and start with Easy. Come back to this article when you get stuck — the framework above applies to every problem in that list.