Dynamic Programming Interview Questions: The Ultimate Guide with Solutions

Dynamic programming is one of the most feared topics in coding interviews, and also one of the most rewarding to master. It appears frequently in interviews at top technology companies and is often the dividing line between candidates who receive offers and those who do not.

The good news is that dynamic programming is a skill that can be learned systematically. Once you understand the core principles and recognize the common patterns, even problems that initially seem impossible become approachable. This guide will take you from the fundamentals through the most commonly tested problems, with complete Python solutions for each.

Table of Contents

• What Is Dynamic Programming?
• When to Use Dynamic Programming
• Memoization vs Tabulation
• The Five-Step Framework for Solving DP Problems
• Classic DP Problems with Solutions
  • Fibonacci Sequence
  • Climbing Stairs
  • 0/1 Knapsack Problem
  • Longest Common Subsequence
  • Coin Change
  • House Robber
  • Edit Distance
  • Longest Increasing Subsequence
  • Unique Paths
  • Partition Equal Subset Sum
• Advanced DP Patterns
• Tips for DP Problems in Interviews
• FAQ
• Conclusion

What Is Dynamic Programming?

Dynamic programming is an optimization technique that solves complex problems by breaking them down into simpler overlapping subproblems. Instead of solving the same subproblem multiple times, DP stores the results of subproblems and reuses them when needed.

A problem is a good candidate for dynamic programming when it has two key properties:

1. Optimal Substructure - The optimal solution to the problem can be constructed from the optimal solutions of its subproblems. For example, the shortest path from A to C through B is the shortest path from A to B plus the shortest path from B to C.

2. Overlapping Subproblems - The same subproblems are solved multiple times during the computation. This is what distinguishes DP from divide-and-conquer, where subproblems are independent.

When both properties are present, dynamic programming can dramatically reduce the time complexity of a solution, often from exponential to polynomial time.

When to Use Dynamic Programming

Recognizing when a problem requires DP is half the battle. Look for these signals:

• The problem asks for an optimal value (minimum, maximum, longest, shortest, or count).
• The problem involves making choices at each step, and each choice affects future options.
• The problem can be broken down into smaller versions of itself.
• A brute-force recursive solution would involve repeated computation of the same inputs.
• The problem involves sequences, strings, or grids where you build up solutions incrementally.

Common problem categories that use DP include: optimization problems, counting problems, string matching and comparison, grid traversal, and decision-making sequences.

Memoization vs Tabulation

There are two primary approaches to implementing dynamic programming, and understanding both is essential for interviews.

Memoization (Top-Down)

Memoization starts with the original problem and recursively breaks it down into subproblems. Results are stored in a cache (usually a dictionary or array) so that each subproblem is solved only once.

# Fibonacci with memoization
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Advantages of memoization:

• Intuitive if you think recursively
• Only solves subproblems that are actually needed
• Easier to derive from a brute-force recursive solution

Disadvantages:

• Recursive call stack can cause stack overflow for very large inputs
• Function call overhead adds constant-factor cost

Tabulation (Bottom-Up)

Tabulation starts with the smallest subproblems and iteratively builds up to the final answer. Results are stored in a table (usually an array) that is filled in order of increasing subproblem size.

# Fibonacci with tabulation
def fib_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]

Advantages of tabulation:

• No recursion, so no risk of stack overflow
• Generally faster due to no function call overhead
• Easier to optimize space (often can reduce from O(n) to O(1))

Disadvantages:

• May solve subproblems that are not needed
• Can be less intuitive for some problems
• Requires careful thought about the order of computation

Which Should You Use in Interviews?

In most interviews, either approach is acceptable. However, here are some guidelines:

• Start with memoization if you find it easier to think about the problem recursively.
• Switch to tabulation if the interviewer asks you to optimize space or if the recursive depth might be too large.
• Be prepared to explain both approaches and their trade-offs.

The Five-Step Framework for Solving DP Problems

Use this framework consistently when tackling any DP problem in an interview:

1. Define the state. What information do you need to represent a subproblem? This becomes your DP array index or memo key.
2. Define the recurrence relation. How does the answer to a subproblem relate to the answers of smaller subproblems? This is the core of the solution.
3. Identify the base cases. What are the smallest subproblems that can be solved directly without further decomposition?
4. Determine the computation order. For tabulation, in what order should you fill in the DP table?
5. Extract the final answer. Where in your DP table or memo is the answer to the original problem?

Classic DP Problems with Solutions

1. Fibonacci Sequence

The Fibonacci sequence is the canonical introduction to dynamic programming. While simple, it perfectly illustrates the concept of overlapping subproblems.

Problem: Compute the nth Fibonacci number.

Recurrence: F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1.

# Space-optimized tabulation - O(n) time, O(1) space
def fibonacci(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

Key insight: You only need the last two values at any point, so you can reduce space from O(n) to O(1).

2. Climbing Stairs

Problem: You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top?

State: dp[i] = number of ways to reach step i.

Recurrence: dp[i] = dp[i-1] + dp[i-2] (you can arrive at step i from step i-1 or step i-2).

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

Time complexity: O(n). Space complexity: O(1).

3. 0/1 Knapsack Problem

Problem: Given n items, each with a weight and a value, determine the maximum value you can carry in a knapsack of capacity W. Each item can be taken at most once.

State: dp[i][w] = maximum value achievable using items 0 through i with capacity w.

Recurrence: For each item, you either include it or skip it: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i]] + values[i]) if weights[i] <= w, otherwise dp[i][w] = dp[i-1][w].

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]
 
# Space-optimized version using 1D array
def knapsack_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
 
    for i in range(n):
        # Traverse backwards to avoid using updated values
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
 
    return dp[capacity]

Time complexity: O(n * W). Space complexity: O(W) for the optimized version.

Key insight: In the 1D optimization, iterating backwards prevents counting an item more than once.

4. Longest Common Subsequence (LCS)

Problem: Given two strings, find the length of their longest common subsequence. A subsequence is a sequence that appears in the same relative order but not necessarily contiguous.

State: dp[i][j] = length of LCS of the first i characters of text1 and the first j characters of text2.

Recurrence: If text1[i-1] == text2[j-1], then dp[i][j] = dp[i-1][j-1] + 1. Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

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]
 
# To also reconstruct the actual subsequence
def lcs_with_reconstruction(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])
 
    # Backtrack to find the subsequence
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if text1[i - 1] == text2[j - 1]:
            result.append(text1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
 
    return ''.join(reversed(result))

Time complexity: O(m _ n). Space complexity: O(m _ n), reducible to O(min(m, n)) if only the length is needed.

5. Coin Change

Problem: Given an array of coin denominations and a target amount, find the minimum number of coins needed to make that amount. You have an unlimited supply of each coin denomination. Return -1 if the amount cannot be made.

State: dp[i] = minimum number of coins needed to make amount i.

Recurrence: dp[i] = min(dp[i - coin] + 1) for each coin denomination where coin <= i.

def coin_change(coins, amount):
    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] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)
 
    return dp[amount] if dp[amount] != float('inf') else -1

Time complexity: O(amount * len(coins)). Space complexity: O(amount).

Variant - Coin Change 2 (Count Combinations):

def coin_change_combinations(coins, amount):
    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]

Key insight: In the combination variant, iterating over coins in the outer loop ensures each combination is counted only once, avoiding duplicate permutations.

6. House Robber

Problem: You are a robber planning to rob houses along a street. Each house has a certain amount of money. Adjacent houses have security systems connected, so you cannot rob two adjacent houses. Find the maximum amount of money you can rob.

State: dp[i] = maximum money you can rob from the first i houses.

Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). At each house, you either skip it (take dp[i-1]) or rob it (take dp[i-2] + nums[i]).

def house_robber(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
 
    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])
 
    for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = curr
 
    return prev1

Time complexity: O(n). Space complexity: O(1).

Variant - House Robber II (Circular Street):

When the houses are arranged in a circle, the first and last houses are adjacent. Solve this by running the linear version twice: once excluding the first house and once excluding the last house, then taking the maximum.

def house_robber_circular(nums):
    if len(nums) == 1:
        return nums[0]
 
    def rob_linear(houses):
        prev2, prev1 = 0, 0
        for money in houses:
            curr = max(prev1, prev2 + money)
            prev2 = prev1
            prev1 = curr
        return prev1
 
    return max(rob_linear(nums[1:]), rob_linear(nums[:-1]))

7. Edit Distance (Levenshtein Distance)

Problem: Given two strings word1 and word2, find the minimum number of operations required to convert word1 to word2. You can insert a character, delete a character, or replace a character.

State: dp[i][j] = minimum operations to convert the first i characters of word1 to the first j characters of word2.

Recurrence:

• If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] (no operation needed)
• Otherwise: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (delete, insert, or replace)

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
 
    # Base cases
    for i in range(m + 1):
        dp[i][0] = i  # Delete all characters from word1
    for j in range(n + 1):
        dp[0][j] = j  # Insert all characters into word1
 
    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]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # Delete
                    dp[i][j - 1],      # Insert
                    dp[i - 1][j - 1]   # Replace
                )
 
    return dp[m][n]

Time complexity: O(m _ n). Space complexity: O(m _ n), reducible to O(min(m, n)).

8. Longest Increasing Subsequence

Problem: Given an integer array, find the length of the longest strictly increasing subsequence.

# O(n^2) DP solution
def length_of_lis(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n  # Each element is an LIS of length 1
 
    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)
 
# O(n log n) solution using binary search
import bisect
 
def length_of_lis_optimized(nums):
    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)

Key insight: The O(n log n) solution maintains an array where tails[i] is the smallest possible tail element for an increasing subsequence of length i+1. Binary search finds the correct position to update.

9. Unique Paths

Problem: A robot is at the top-left corner of an m x n grid. It can only move right or down. How many unique paths are there to the bottom-right corner?

def unique_paths(m, n):
    dp = [1] * n  # First row: only one way to reach each cell
 
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
 
    return dp[n - 1]

Time complexity: O(m * n). Space complexity: O(n).

Variant with obstacles:

def unique_paths_with_obstacles(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    dp[0] = 1 if grid[0][0] == 0 else 0
 
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[j] = 0
            elif j > 0:
                dp[j] += dp[j - 1]
 
    return dp[n - 1]

10. Partition Equal Subset Sum

Problem: Given a non-empty array of positive integers, determine if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Insight: This reduces to finding a subset with sum equal to total_sum / 2, which is a variant of the 0/1 knapsack problem.

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
 
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
 
    for num in nums:
        # Traverse backwards to ensure each number is used at most once
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
 
    return dp[target]

Time complexity: O(n * target). Space complexity: O(target).

Advanced DP Patterns

Once you are comfortable with the classic problems above, these advanced patterns appear in harder interview questions:

Interval DP

Used when the problem involves merging or splitting intervals. The subproblem is defined over a contiguous range [i, j].

Example: Matrix Chain Multiplication, Burst Balloons, Minimum Cost to Merge Stones.

Bitmask DP

Used when the state involves a subset of elements, typically when n is small (n <= 20). The state is represented as a bitmask.

Example: Travelling Salesman Problem, Minimum Cost to Visit Every Node.

DP on Trees

Used when the problem structure is a tree rather than a sequence or grid. The DP state is defined per subtree.

Example: Maximum Path Sum in Binary Tree, House Robber III.

Digit DP

Used for counting numbers in a range that satisfy certain digit-based constraints.

Example: Count numbers up to N where no two adjacent digits are the same.

DP with State Compression

When the state space is too large for a naive DP table, techniques like rolling arrays, bitmask compression, or profile DP can make the problem tractable.

Tips for DP Problems in Interviews

1. Start with brute-force recursion. Write a recursive solution first, even if it is exponential. This helps you identify the subproblem structure and recurrence relation.

2. Identify repeated work. Add print statements to your recursive solution to see which subproblems are computed multiple times. This confirms that DP is applicable.

3. Add memoization. Convert your recursive solution to a memoized version by caching results. This is often the fastest path to a correct solution in an interview.

4. Convert to tabulation if needed. If the interviewer asks for an iterative solution or space optimization, convert your memoized solution to bottom-up tabulation.

5. Optimize space. Many 2D DP problems only depend on the previous row, allowing you to reduce space from O(m * n) to O(n).

6. Draw the DP table. For 2D problems, manually filling in a small DP table on paper helps you verify your recurrence and catch off-by-one errors.

7. Practice identifying the state. The hardest part of DP is defining what information your state needs to capture. Practice this deliberately.

8. Use Phantom Code for guided practice. Phantom Code provides AI-powered feedback on your DP solutions, helping you identify where your approach breaks down and suggesting optimizations you might have missed.

FAQ

How important is dynamic programming in interviews?

DP is one of the most commonly tested topics at top technology companies. It appears in roughly 20-30% of coding interviews at companies like Google, Microsoft, Amazon, and Apple. Meta is a notable exception, as they explicitly state they do not ask DP questions.

Should I memorize DP solutions?

No. Memorizing solutions without understanding the underlying principles will fail you when you encounter a new variation. Instead, focus on understanding the problem-solving framework: defining states, writing recurrences, and identifying base cases.

What is the best order to learn DP problems?

Start with 1D problems (Fibonacci, climbing stairs, house robber), then move to 2D problems (LCS, edit distance, knapsack), and finally tackle advanced patterns (interval DP, bitmask DP). This progression builds your intuition incrementally.

How many DP problems should I practice?

Solving 30 to 50 well-chosen DP problems with deep understanding is more valuable than rushing through 100 problems superficially. Focus on one problem category at a time and make sure you can solve variations before moving on.

Is memoization or tabulation better for interviews?

Both are valid. Memoization is generally faster to write and easier to derive from a recursive solution, making it a good default choice under time pressure. Be prepared to discuss the trade-offs and convert between the two approaches.

Conclusion

Dynamic programming is a learnable skill, not a talent. The key is to practice deliberately, understand the underlying patterns, and build your intuition for defining states and recurrences. Start with the classic problems in this guide, master the five-step framework, and gradually work your way up to harder problems.

Use Phantom Code as your practice companion to get real-time feedback on your solutions and accelerate your preparation. With consistent effort and the right approach, you will find that DP problems become one of your strongest areas in coding interviews.