Dynamic Programming Interview Questions and Answers

10 questions

What is dynamic programming?
Dynamic programming builds an answer from smaller subproblems and stores each one so it is computed once. It applies when subproblems overlap and the best answer is built from best sub-answers. Naive Fibonacci is exponential; storing results makes it O(n). Say what dp[i] means before the transition.
Practice it: Climbing Stairs, Fibonacci Number

How many calls does a naive recursive `fib(10)` make in Python?

Python

calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

fib(10)
print(calls)

Every call with n of 2 or more makes two more, so fib(10) makes 177 calls, 2 * F(n + 1) - 1, growing like 1.618^n. Caching cuts it to one call per n:

Python

from functools import lru_cache

calls = 0

@lru_cache(maxsize=None)
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10), calls)

That prints 55 and 11 calls.

Practice it: Fibonacci Number

What is the difference between memoization and tabulation?
Memoization is top-down: write the recursion and cache each result. Tabulation is bottom-up: fill a table from the smallest subproblems so dependencies are always ready. Same time complexity.
Python
from functools import lru_cache @lru_cache(maxsize=None) def ways_memo(n): # top-down if n <= 1: return 1 return ways_memo(n - 1) + ways_memo(n - 2) def ways_table(n): # bottom-up dp = [1, 1] + [0] * (n - 1) for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] print(ways_memo(10), ways_table(10))
Memoization computes only needed states but can hit the recursion limit; tabulation makes it easy to keep only the rows you need.
Practice it: Climbing Stairs

What is the difference between greedy and dynamic programming? Show a case where greedy fails.

Greedy takes the locally best choice and never revisits it; DP tries every choice per subproblem and keeps the best. Greedy is only correct when you can prove the local choice is safe. Coins [1, 3, 4] for 6 break it: greedy gives 4 + 1 + 1, the best is 3 + 3.

Python

def greedy_coins(coins, amount):
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count if amount == 0 else -1

def dp_coins(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

print(greedy_coins([1, 3, 4], 6), dp_coins([1, 3, 4], 6))

Greedy is right for interval scheduling and for US coins.

Practice it: Coin Change, Jump Game

How do you solve the house robber problem?
Rob house i (its money plus the best up to two houses back) or skip it (the best up to the previous house): best[i] = max(best[i - 1], best[i - 2] + money[i]). Two variables suffice: O(n) time, O(1) space.
Python
def rob(money): prev2 = prev1 = 0 for m in money: prev2, prev1 = prev1, max(prev1, prev2 + m) return prev1 print(rob([2, 7, 9, 3, 1])) print(rob([2, 1, 1, 2]))
The second case shows taking every other house fails: the best, 4, robs the first and last.
Practice it: House Robber
How many right and down paths does the DP table count in a 3 × 3 grid?
Python
rows, cols = 3, 3 dp = [[1] * cols for _ in range(rows)] for r in range(1, rows): for c in range(1, cols): dp[r][c] = dp[r - 1][c] + dp[r][c - 1] print(dp[-1][-1])
Paths into a cell come from the cell above plus the cell to its left, and the first row and column are all 1, so the last cell of a 3 × 3 grid is 6, which is C(4, 2). Keeping one row cuts space to O(cols).
Practice it: Unique Paths
How do you solve the 0/1 knapsack problem?
dp[w] is the best value with capacity w. For each item, loop w from high to low: dp[w] = max(dp[w], dp[w - weight] + value). Going downward uses each item once; going upward allows reuse, the unbounded knapsack. O(n × W) time, O(W) space.
Python
def knapsack(items, capacity): dp = [0] * (capacity + 1) for weight, value in items: for w in range(capacity, weight - 1, -1): dp[w] = max(dp[w], dp[w - weight] + value) return dp[capacity] items = [(1, 1), (3, 4), (4, 5), (5, 7)] # (weight, value) print(knapsack(items, 7))
That is pseudo-polynomial: slow when W is huge.
Practice it: Partition Equal Subset Sum
How do you find the longest increasing subsequence, and how do you get it to O(n log n)?
The O(n²) DP sets dp[i] to the longest increasing subsequence ending at i. For O(n log n), keep tails, the smallest last value of an increasing subsequence of each length; each number extends it or replaces the first tail not smaller, found by binary search.
Python
from bisect import bisect_left def lis_length(nums): tails = [] for x in nums: i = bisect_left(tails, x) if i == len(tails): tails.append(x) else: tails[i] = x return len(tails) print(lis_length([10, 9, 2, 5, 3, 7, 101, 18]))
Only the length of tails is meaningful, not its contents.
Practice it: Longest Increasing Subsequence

How do you solve longest common subsequence and edit distance?

Both fill a table where dp[i][j] covers the first i characters of one string and the first j of the other. On a match, extend the diagonal; otherwise LCS drops a character from either string, and edit distance takes 1 plus the cheapest of insert, delete or replace. O(m × n).

Python

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

def edit_distance(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        dp[i][0] = i
    for j in range(len(b) + 1):
        dp[0][j] = j
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[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[-1][-1]

print(lcs("abcde", "ace"), edit_distance("horse", "ros"))

Base cases: an empty prefix has LCS 0, and emptying a prefix of length i costs i deletions.

Practice it: Longest Common Subsequence, Edit Distance

How do you recognize that a problem needs dynamic programming?
Look for a count of ways, a minimum or maximum, or "is it possible", where a big input's answer builds on smaller ones and brute force repeats subproblems. Then:
1. Define the state: "dp[i] is the fewest coins for amount i".
2. Write the transition.
3. Set the base cases.
4. Pick the fill order, or memoize.
Listing every solution, rather than counting, is usually backtracking.
Practice it: Word Break, Decode Ways

What is dynamic programming?

How many calls does a naive recursive fib(10) make in Python?

What is the difference between memoization and tabulation?

What is the difference between greedy and dynamic programming? Show a case where greedy fails.

How do you solve the house robber problem?

How many right and down paths does the DP table count in a 3 × 3 grid?

How do you solve the 0/1 knapsack problem?

How do you find the longest increasing subsequence, and how do you get it to O(n log n)?

How do you solve longest common subsequence and edit distance?

How do you recognize that a problem needs dynamic programming?

Learn to code with Coddy

How many calls does a naive recursive `fib(10)` make in Python?