Dynamic Programming Interview Questions: A Framework

Dynamic programming solves problems by breaking them into overlapping subproblems and storing results to avoid redundant computation. It is the most feared pattern in FAANG interviews, but the key is recognizing the right problems and following a systematic approach.

When to Use Dynamic Programming

Use DP when:

• The problem asks for the "best," "minimum," "maximum," or "count of ways"
• You can define the problem in terms of smaller subproblems
• The subproblems overlap (the same subproblem is solved multiple times)
• The problem has optimal substructure (optimal solution contains optimal solutions to subproblems)
• Brute force would be exponential time

Do NOT use DP when:

• The problem is greedy (locally optimal choices lead to globally optimal)
• There are no overlapping subproblems (use divide and conquer)
• The problem asks for a yes/no answer without counting (often DFS with memoization is simpler)

The Trigger Pattern

The problem says "minimum number of" or "ways to" → DP. The problem says "can you reach" → DFS + memoization. The problem says "maximum profit" with constraints → DP. The problem says "longest" → DP on sequences.

The DP Framework: 4 Steps

1. Define the state: What are the subproblems? What does dp[i] or dp[i][j] represent?
2. Write the recurrence: How does dp[i] relate to dp[i-1], dp[i-2], etc.?
3. Identify base cases: What are the smallest subproblems with known answers?
4. Determine traversal order: Fill the table bottom-up (or top-down with memoization).

Memoization vs Tabulation

Memoization is better for interviews because you write the natural recursive solution and add caching. Tabulation is better for production because it avoids recursion overhead.

Coin Change

Given coin denominations and a target amount, find the minimum number of coins needed to make the amount. This is the classic DP problem.

def coin_change(coins, amount):
    # dp[i] = minimum coins needed to make amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins needed for amount 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1

    return dp[amount] if dp[amount] != float('inf') else -1

Why this works: For each amount i, try every coin. If the coin fits (coin <= i), the answer is 1 + dp[i - coin]. Take the minimum across all coins. dp[0] = 0 is the base case because you need zero coins to make amount zero.

Time: O(amount × len(coins)). Space: O(amount).

Memoization version:

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

Longest Increasing Subsequence (LIS)

Given an integer array, find the length of the longest strictly increasing subsequence. This is the most commonly asked DP problem at FAANG companies.

def length_of_lis(nums):
    if not nums:
        return 0

    # dp[i] = length of LIS ending at index i
    dp = [1] * len(nums)

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

    return max(dp)

Why this works: For each element, check all previous elements. If a previous element is smaller, it can extend the subsequence ending at that element. dp[i] is the best extension from all valid previous elements.

Time: O(n²). Space: O(n).

Optimized O(n log n) version using binary search:

import bisect

def length_of_lis_optimized(nums):
    # tails[i] = smallest tail element for LIS of length i+1
    tails = []

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

    return len(tails)

The tails array is always sorted, so binary search finds the correct position in O(log n). The final answer is the length of tails.

Edit Distance

Given two strings, find the minimum number of operations (insert, delete, replace) needed to convert one string to the other. This is the hardest common DP problem.

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)

    # dp[i][j] = edit distance between word1[:i] and word2[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases: converting empty string to word2[:j] requires j inserts
    for j in range(n + 1):
        dp[0][j] = j

    # Base cases: converting word1[:i] to empty string requires i deletes
    for i in range(m + 1):
        dp[i][0] = i

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # Characters match, no operation
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # Delete from word1
                    dp[i][j - 1],      # Insert into word1
                    dp[i - 1][j - 1]   # Replace in word1
                )

    return dp[m][n]

Why this works: Each cell dp[i][j] represents the minimum edits to convert word1[:i] to word2[:j]. If characters match, no operation is needed — take the diagonal value. If they differ, take the minimum of delete, insert, or replace plus one.

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

Space-optimized version using two rows:

def edit_distance_optimized(word1, word2):
    m, n = len(word1), len(word2)

    prev = list(range(n + 1))

    for i in range(1, m + 1):
        curr = [i] + [0] * n
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
        prev = curr

    return prev[n]

Only two rows are needed at any time, reducing space from O(m × n) to O(n).

Coin Change II (Number of Ways)

A variation that counts the number of ways to make the amount instead of finding the minimum coins.

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1  # One way to make amount 0: use no coins

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

Why this works: The outer loop iterates over coins to avoid counting permutations as different combinations. For each coin, update all amounts it can contribute to. dp[i] accumulates the number of ways to reach amount i.

Time: O(amount × len(coins)). Space: O(amount).

Common Mistakes

1. Not defining the state clearly. Before writing code, explain what dp[i] or dp[i][j] represents. A unclear state definition leads to incorrect recurrences. Write the definition in words before translating to code.

2. Wrong loop order in tabulation. If dp[i] depends on dp[i+1], you must iterate backwards. If it depends on dp[i-1], iterate forwards. The traversal order must match the dependency direction.

3. Forgetting base cases. Base cases are the foundation. dp[0] = 0 for coin change, dp[0][j] = j for edit distance. Without correct base cases, every other value is wrong.

4. Not handling edge cases. Empty strings, zero amounts, single elements. Always check if the input is empty before accessing indices.

5. Confusing subsequence and substring. A subsequence can skip characters (LIS). A substring must be contiguous. The DP recurrence is different for each. Subsequence uses dp[i] = best over all j < i. Substring uses dp[i][j] = result for substring from i to j.

Practice Problems

Start with these problems to master dynamic programming:

1. Coin Change — The entry-level DP problem. Master the minimum coins pattern before moving to harder problems.
2. Longest Increasing Subsequence — The most commonly asked DP problem. Practice both O(n²) and O(n log n) solutions.
3. Edit Distance — The classic 2D DP problem. Tests state design for two-string problems.
4. Coin Change II — Counting variations of the same problem. Tests whether you understand the difference between minimum and counting.
5. Climbing Stairs — The simplest DP problem. Good warmup for understanding state transitions.

Practice What You Learned

Ready to put this into practice? Try a mock coding interview with an AI interviewer who can give you dynamic programming problems and evaluate your approach in real time.

Frequently Asked Questions