Dynamic Programming Tutorial: Master 5 Essential DP Patterns Coding Interviews

Why Dynamic Programming Felt Like Black Magic (Until It Didn't)

I still remember my first encounter with Dynamic Programming. The interviewer asked me to solve the classic coin change problem, and I stared blankly at the whiteboard. I knew it was DP—everyone says "optimization + overlapping subproblems = DP"—but I had no idea where to start. My attempted recursive solution spiraled into an incomprehensible mess of base cases and recursive calls.

Fast forward six months, and I was confidently solving hard-level DP problems in interviews. What changed? I stopped trying to memorize individual solutions and started recognizing that virtually all DP problems fall into just 5 core patterns. Once I learned these patterns, DP transformed from mysterious black magic into a systematic, almost mechanical process.

In this guide, I'll share the exact pattern-based framework that took me from DP confusion to DP confidence. No abstract theory or mathematical proofs—just practical patterns, clear intuition, and the templates you need to solve 95% of DP interview questions.

The Mental Shift That Makes DP Click

Here's the insight that changed everything for me: DP problems aren't about clever tricks—they're about recognizing which of the 5 patterns applies, then filling in the template.

Think of it like cooking. Once you know the five mother sauces in French cuisine, you can create hundreds of dishes by applying the right sauce pattern and varying the ingredients. DP is exactly the same—once you know the five core patterns, you just identify which one fits and adapt it to the specific problem.

The three-step DP process:

1. Recognize the pattern from the problem statement
2. Write the recursive solution (define states and transitions)
3. Optimize with memoization or tabulation

That's it. No magic, just systematic pattern application.

How to Recognize a DP Problem

Before diving into the five patterns, let's talk about recognition. When should your brain scream "Dynamic Programming"?

Three indicators that scream DP:

1. The problem asks for an optimal solution - maximum, minimum, longest, shortest
2. You can break it into overlapping subproblems - solving the same smaller problem multiple times
3. Future decisions depend on previous decisions - choices affect what's possible later

Classic DP keywords:

• "Maximum/minimum value"
• "Longest/shortest sequence"
• "Count number of ways"
• "Is it possible to..."
• "Optimize"

If you see these, immediately think: "Could this be DP?"

The Five DP Pattern Families

Let me introduce the five patterns that cover virtually every DP problem you'll encounter. Each pattern has a distinct "signature" that helps you recognize it from the problem statement.

Pattern 1: The 0/1 Knapsack Family

Signature: "Choose elements (each used once) to achieve a target while optimizing some value."

When to recognize:

• Each element can be picked at most once
• Binary choice at each step: include or exclude
• Often involves "subset" or "partition" keywords
• Weight/value or cost/benefit structure

The core intuition:

For each item, you have exactly two choices:

1. Include it (if it fits) → solve for remaining items with reduced capacity
2. Exclude it → solve for remaining items with same capacity

Template:

def knapsack_pattern(items, capacity):
    """
    0/1 Knapsack template: each item picked at most once.
    State: (current_index, remaining_capacity)
    """
    n = len(items)
    memo = {}

    def dp(index, remaining):
        # Base case: no items left or no capacity
        if index < 0 or remaining == 0:
            return 0

        # Check memo
        if (index, remaining) in memo:
            return memo[(index, remaining)]

        # Option 1: Skip current item
        exclude = dp(index - 1, remaining)

        # Option 2: Include current item (if it fits)
        include = 0
        if items[index].weight <= remaining:
            include = items[index].value + dp(index - 1, remaining - items[index].weight)

        # Store and return best option
        memo[(index, remaining)] = max(include, exclude)
        return memo[(index, remaining)]

    return dp(n - 1, capacity)

Problem family members:

1. Classic 0/1 Knapsack - Maximize value with weight constraint
2. Subset Sum - Can you achieve exact target sum?
3. Equal Sum Partition - Can you partition into two equal subsets?
4. Target Sum - Count ways to assign +/- to reach target
5. Minimum Subset Sum Difference - Minimize difference between two subsets

The build-upon strategy:

Here's what makes pattern recognition so powerful: Once you solve the base 0/1 Knapsack, all variations are just tweaks to the same template!

• Subset Sum? Same template, but return boolean instead of maximum value
• Count of Subsets? Same template, but add instead of max, and count ways instead of values
• Equal Partition? Same template with target = sum(array) / 2

Let me show you with Subset Sum:

def subset_sum(nums, target):
    """
    Can we select elements that sum to target?
    Same pattern as knapsack, different return type.
    """
    n = len(nums)
    memo = {}

    def dp(index, remaining):
        # Base cases
        if remaining == 0:
            return True  # Found target!
        if index < 0 or remaining < 0:
            return False

        if (index, remaining) in memo:
            return memo[(index, remaining)]

        # Include or exclude current number
        include = dp(index - 1, remaining - nums[index])
        exclude = dp(index - 1, remaining)

        memo[(index, remaining)] = include or exclude
        return memo[(index, remaining)]

    return dp(n - 1, target)

Test: subset_sum([3, 34, 4, 12, 5, 2], 9) → True (4+5 or 4+3+2)

See? Same structure, just adapted to the question being asked!

Pattern 2: The Unbounded Knapsack Family

Signature: "Choose elements (can reuse) to achieve a target while optimizing some value."

When to recognize:

• Items can be used unlimited times
• Keywords like "unlimited supply" or "reusable"
• Coin change problems (unlimited coins)
• Rod cutting problems

The key difference from 0/1 Knapsack:

When you "include" an item, you DON'T move to the next index—you stay at the same index because you can reuse it!

Template:

def unbounded_knapsack_pattern(items, capacity):
    """
    Unbounded knapsack: items can be reused.
    State: (current_index, remaining_capacity)
    """
    n = len(items)
    memo = {}

    def dp(index, remaining):
        # Base case
        if index < 0 or remaining == 0:
            return 0

        if (index, remaining) in memo:
            return memo[(index, remaining)]

        # Option 1: Skip current item (move to next)
        exclude = dp(index - 1, remaining)

        # Option 2: Include current item (STAY at same index!)
        include = 0
        if items[index].weight <= remaining:
            include = items[index].value + dp(index, remaining - items[index].weight)  # Note: index, not index-1

        memo[(index, remaining)] = max(include, exclude)
        return memo[(index, remaining)]

    return dp(n - 1, capacity)

Classic problem: Coin Change

def coin_change(coins, amount):
    """
    Minimum coins needed to make amount.
    Unbounded knapsack pattern with minimization.
    """
    memo = {}

    def dp(index, remaining):
        # Base cases
        if remaining == 0:
            return 0  # No coins needed
        if index < 0:
            return float('inf')  # Impossible

        if (index, remaining) in memo:
            return memo[(index, remaining)]

        # Exclude current coin
        exclude = dp(index - 1, remaining)

        # Include current coin (can reuse)
        include = float('inf')
        if coins[index] <= remaining:
            include = 1 + dp(index, remaining - coins[index])

        memo[(index, remaining)] = min(include, exclude)
        return memo[(index, remaining)]

    result = dp(len(coins) - 1, amount)
    return result if result != float('inf') else -1

Test: coin_change([1, 2, 5], 11) → 3 (5+5+1)

Problem family members:

1. Coin Change - Minimum coins to make amount
2. Coin Change II - Count ways to make amount
3. Rod Cutting - Maximum value by cutting rod
4. Minimum Cost to Fill Knapsack - Optimization variant

Pattern 3: The Longest Common Subsequence (LCS) Family

Signature: "Compare two sequences to find common patterns or transform one into another."

When to recognize:

• Two input strings/arrays to compare
• Keywords: "common," "matching," "transform"
• Edit distance, alignment problems
• Substring vs subsequence problems

The core intuition:

For two strings, at each position you have two characters. Either:

1. They match → include this character, move both pointers
2. They don't match → try excluding from either string, take best

Template:

def lcs_pattern(s1, s2):
    """
    Longest Common Subsequence pattern.
    State: (index in s1, index in s2)
    """
    m, n = len(s1), len(s2)
    memo = {}

    def dp(i, j):
        # Base case: reached end of either string
        if i < 0 or j < 0:
            return 0

        if (i, j) in memo:
            return memo[(i, j)]

        # Characters match: include and move both pointers
        if s1[i] == s2[j]:
            result = 1 + dp(i - 1, j - 1)
        else:
            # Don't match: try excluding from either string
            result = max(dp(i - 1, j), dp(i, j - 1))

        memo[(i, j)] = result
        return result

    return dp(m - 1, n - 1)

Test: lcs_pattern("ABCDGH", "AEDFHR") → 3 ("ADH")

Problem family members:

1. Longest Common Subsequence - Base problem
2. Longest Common Substring - Requires consecutive characters
3. Edit Distance - Minimum operations to transform
4. Minimum Insertions/Deletions - Make strings equal
5. Shortest Common Supersequence - Shortest string containing both

Example: Edit Distance (Levenshtein Distance)

def edit_distance(word1, word2):
    """
    Minimum operations (insert/delete/replace) to transform word1 to word2.
    LCS pattern with three choices instead of two.
    """
    m, n = len(word1), len(word2)
    memo = {}

    def dp(i, j):
        # Base cases
        if i < 0:
            return j + 1  # Insert j+1 characters
        if j < 0:
            return i + 1  # Delete i+1 characters

        if (i, j) in memo:
            return memo[(i, j)]

        # Characters match: no operation needed
        if word1[i] == word2[j]:
            result = dp(i - 1, j - 1)
        else:
            # Three choices: insert, delete, or replace
            insert = 1 + dp(i, j - 1)
            delete = 1 + dp(i - 1, j)
            replace = 1 + dp(i - 1, j - 1)
            result = min(insert, delete, replace)

        memo[(i, j)] = result
        return result

    return dp(m - 1, n - 1)

Test: edit_distance("horse", "ros") → 3 (replace h→r, remove o, remove e)

Pattern 4: The Longest Increasing Subsequence (LIS) Family

Signature: "Find optimal increasing/decreasing patterns in a sequence."

When to recognize:

• Single array/sequence
• Looking for increasing or decreasing subsequences
• Keywords: "longest increasing," "maximum sum increasing"
• Building towers, stacking boxes problems

The core intuition:

For each element, you decide: "Should I extend an existing subsequence that ends with a smaller element, or start fresh?"

Template:

def lis_pattern(nums):
    """
    Longest Increasing Subsequence pattern.
    State: (current_index)
    For each position, try all previous positions to extend from.
    """
    n = len(nums)
    if n == 0:
        return 0

    # dp[i] = length of LIS ending at index i
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Test: lis_pattern([10, 9, 2, 5, 3, 7, 101, 18]) → 4 (2,3,7,101)

Problem family members:

1. Longest Increasing Subsequence - Base problem
2. Maximum Sum Increasing Subsequence - Track sum instead of length
3. Longest Bitonic Subsequence - Increasing then decreasing
4. Longest Chain - Pairs forming chains
5. Russian Doll Envelopes - 2D LIS variant

The Binary Search optimization:

Standard LIS is O(n²), but with binary search it becomes O(n log n):

def lis_binary_search(nums):
    """
    O(n log n) LIS using binary search.
    Maintain array of smallest tail elements.
    """
    from bisect import bisect_left

    tails = []

    for num in nums:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num

    return len(tails)

This optimization is worth knowing—it's a common follow-up question!

Pattern 5: The Matrix Chain Multiplication (MCM) Family

Signature: "Try all ways to partition/split an interval, choose optimal."

When to recognize:

• Problems about "partitioning" or "splitting"
• Keywords: "minimum cost," "optimal parenthesization"
• Palindrome partitioning, burst balloons
• Trying all ways to break down a problem

The core intuition:

For a range i, j, try every possible partition point k:

• Solve left part i, k
• Solve right part k+1, j
• Combine results with cost of merging

Template:

def mcm_pattern(arr, i, j):
    """
    Matrix Chain Multiplication pattern.
    State: (left_index, right_index)
    Try all partition points k between i and j.
    """
    memo = {}

    def dp(i, j):
        # Base case: single element or invalid range
        if i >= j:
            return 0

        if (i, j) in memo:
            return memo[(i, j)]

        # Try all partition points
        min_cost = float('inf')
        for k in range(i, j):
            # Cost = left part + right part + cost to merge
            cost = dp(i, k) + dp(k + 1, j) + merge_cost(i, k, j)
            min_cost = min(min_cost, cost)

        memo[(i, j)] = min_cost
        return min_cost

    return dp(i, j)

Classic problem: Palindrome Partitioning

def min_palindrome_partitions(s):
    """
    Minimum cuts to partition string into palindromes.
    MCM pattern: try all partition points.
    """
    n = len(s)

    # Helper: check if substring is palindrome
    def is_palindrome(s, i, j):
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

    memo = {}

    def dp(i, j):
        # Base case: empty or single character
        if i >= j or is_palindrome(s, i, j):
            return 0

        if (i, j) in memo:
            return memo[(i, j)]

        # Try all partition points
        min_cuts = float('inf')
        for k in range(i, j):
            # Only partition if left part is palindrome
            if is_palindrome(s, i, k):
                cuts = 1 + dp(k + 1, j)
                min_cuts = min(min_cuts, cuts)

        memo[(i, j)] = min_cuts
        return min_cuts

    return dp(0, n - 1)

Test: min_palindrome_partitions("aab") → 1 (partition into "aa" and "b")

Problem family members:

1. Matrix Chain Multiplication - Base problem
2. Palindrome Partitioning - Minimum cuts for palindromes
3. Burst Balloons - Maximize score bursting balloons
4. Boolean Parenthesization - Count ways to parenthesize
5. Scrambled String - Check if strings are scrambled versions

From Recursion to Memoization to Tabulation

Once you've identified the pattern and written the recursive solution, optimization is mechanical:

Step 1: Recursive Solution (Top-Down)

Start here. Define your state, base cases, and transitions clearly.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Problem: Exponential time due to repeated calculations.

Step 2: Memoization (Top-Down DP)

Add a memo dictionary to cache results.

def fibonacci_memo(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

Benefit: Easy to implement, keeps recursive structure. Time: O(n), Space: O(n).

Step 3: Tabulation (Bottom-Up DP)

Build solution iteratively from smallest subproblems.

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

Benefit: No recursion overhead, easier to optimize space. Time: O(n), Space: O(n).

Step 4: Space Optimization

Often you only need last few states.

def fibonacci_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

Benefit: Time: O(n), Space: O(1).

The Pattern Recognition Flowchart

When you see a DP problem in an interview:

Step 1: Identify the pattern

• Choosing items (each once)? → 0/1 Knapsack
• Choosing items (reusable)? → Unbounded Knapsack
• Comparing two sequences? → LCS Family
• Finding increasing patterns? → LIS Family
• Partitioning intervals? → MCM Family

Step 2: Define your state

• What information do I need to track?
• What changes at each step?

Step 3: Write the recursive solution

• What are my base cases?
• What are my choices at each step?
• How do I combine results?

Step 4: Optimize

• Add memoization (easiest)
• Or convert to tabulation (more optimal)
• Space optimize if needed

Common Mistakes and How to Avoid Them

Mistake 1: Forgetting Base Cases

Always handle edge cases explicitly. Missing base cases lead to infinite recursion or incorrect results.

# Good practice
if n == 0:
    return base_case_0
if n == 1:
    return base_case_1

Mistake 2: Wrong State Definition

Your state must uniquely identify each subproblem. If two different scenarios map to the same state, you'll get wrong answers.

Mistake 3: Incorrect Transition Logic

Double-check your recurrence relation. Are you combining results correctly? Are you trying all necessary options?

Mistake 4: Off-by-One Errors in Tabulation

When converting from recursion to tabulation, indices often shift. Check your loop bounds carefully.

My Learning Journey: From Confusion to Confidence

Here's the practice strategy that worked for me:

Week 1-2: Master Pattern 1 (0/1 Knapsack)

Solve every problem in the Knapsack family. Really understand how each variation builds on the base problem.

• Problems solved: 15-20
• Key insight: Same template, different return values/conditions

Week 3: Learn Pattern 3 (LCS)

Two-sequence problems have a different flavor. Get comfortable with 2D state.

• Problems solved: 10-15
• Key insight: Match or don't match, that's the question

Week 4: Patterns 2, 4, 5

Once you have two patterns down, the others come faster.

• Problems solved: 15-20 across all three patterns
• Key insight: Recognition becomes automatic

Week 5-6: Mixed Practice

Solve problems without looking at the pattern type. Focus on recognition.

• Problems solved: 30-40 mixed
• Key insight: Pattern recognition in 30 seconds or less

Real Interview Success Story

I was asked: "Given an array, find the maximum sum of elements with no two adjacent elements selected."

My thought process:

1. "Optimization problem with choices → DP"
2. "For each element: include it (can't take previous) or exclude it"
3. "This looks like a simplified 0/1 Knapsack!"

I coded it in 10 minutes:

def max_sum_non_adjacent(nums):
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]

    memo = {}

    def dp(i):
        if i < 0:
            return 0
        if i in memo:
            return memo[i]

        # Include current: add value, skip previous
        include = nums[i] + dp(i - 2)
        # Exclude current: take previous
        exclude = dp(i - 1)

        memo[i] = max(include, exclude)
        return memo[i]

    return dp(n - 1)

The interviewer asked, "How did you solve it so quickly?" I explained the pattern-based approach, and they were genuinely impressed.

Conclusion: Your DP Mastery Roadmap

Dynamic Programming doesn't have to be intimidating. Here's what you need to remember:

1. Five patterns cover 95% of problems - Learn these deeply, not hundreds of individual solutions
2. Recognition is the superpower - Spend time identifying which pattern applies
3. Start with recursion - Get the logic right first, optimize later
4. Practice each pattern family - Build solutions upon the base problem

The journey from "DP is black magic" to "DP is just pattern matching" takes focused practice. But once you make that shift, DP problems become some of the most satisfying to solve.

Start with 0/1 Knapsack. Master every variation. Then move to LCS. Before you know it, you'll be the one explaining DP to others.

Remember: every DP expert was once a beginner confused by recursive relations. The difference is they practiced systematically, focusing on patterns rather than memorizing solutions.

Happy coding, and may your memoization always hit the cache!

If you found this pattern-based approach helpful, share it with others struggling with DP. Understanding these five patterns is the key that unlocks all of Dynamic Programming. If this guide helped you finally understand dynamic programming or solve DP interview questions, I'd love to hear about it! Connect with me on Twitter or LinkedIn.

Support My Work

If this guide helped you finally understand Dynamic Programming, transformed how you approach optimization problems, or gave you the confidence to tackle DP in interviews, I'd really appreciate your support! Creating comprehensive, free content like this takes significant time and effort. Your support helps me continue sharing knowledge and creating more helpful resources for students like you.

☕ Buy me a coffee - Every contribution, big or small, means the world to me and keeps me motivated to create more content!

Cover image by Marcin Jozwiak on Unsplash