Dynamic Programming Interview Questions

February 26, 2026 • By Surya Singh • DSA • Dynamic Programming • Memoization • Interview

Dynamic programming interview questions — memoization, tabulation, and optimal substructure.

DSADynamic ProgrammingMemoizationInterview

Key Takeaways

  • 1DP solves problems by breaking them into overlapping subproblems and storing results to avoid recomputation.
  • 2Two main approaches: top-down (memoization, recursive) and bottom-up (tabulation, iterative).
  • 3Identify optimal substructure (optimal solution uses optimal subsolutions) and overlapping subproblems.
  • 4Classic problems: Fibonacci, coin change, longest common subsequence, knapsack, edit distance.

The questions below are commonly asked in technical interviews. Each answer is written to help you understand the concept clearly and explain it confidently. Focus on understanding the "why" behind each answer—that is what interviewers care about.

In this guide

Interview Questions & Answers

What is dynamic programming and how is it different from recursion?

Dynamic programming is an optimization technique for problems with overlapping subproblems. Plain recursion solves the same subproblem many times (e.g., Fibonacci recalculates fib(n-2) when computing fib(n) and fib(n-1)). DP stores the result of each subproblem—either in a memo (top-down) or a table (bottom-up)—so each subproblem is solved only once. The key is recognizing when subproblems repeat. If they do not overlap, simple recursion or divide-and-conquer is enough.

// Fibonacci: Recursion (slow) vs DP Tabulation (fast)
// Plain recursion - O(2^n)
int FibRec(int n) => n <= 1 ? n : FibRec(n-1) + FibRec(n-2);

// DP Tabulation - O(n)
int FibDp(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++)
        (a, b) = (b, a + b);
    return b;
}

What is memoization vs tabulation?

Memoization is top-down: you write a recursive function and cache results. When the function is called with a state you have seen before, return the cached value instead of recursing. Tabulation is bottom-up: you fill a table iteratively, starting from the smallest subproblems. For Fibonacci, memoization: fib(n) checks cache, else computes fib(n-1)+fib(n-2) and caches. Tabulation: create an array dp, set dp[0]=0, dp[1]=1, then loop i from 2 to n, dp[i]=dp[i-1]+dp[i-2]. Both are O(n) time, O(n) space; tabulation can sometimes optimize space to O(1) if you only need the last few values.

// Memoization (top-down)
int FibMemo(int n, Dictionary<int,int>? memo = null) {
    memo ??= new Dictionary<int, int>();
    if (n <= 1) return n;
    if (memo.TryGetValue(n, out var v)) return v;
    memo[n] = FibMemo(n - 1, memo) + FibMemo(n - 2, memo);
    return memo[n];
}

// Tabulation (bottom-up)
int FibTab(int n) {
    if (n <= 1) return n;
    var dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

How do I identify if a problem can be solved with DP?

Look for two properties: optimal substructure (the best solution for the whole problem is built from the best solutions of subproblems) and overlapping subproblems (the same subproblem appears many times). For example, in the coin change problem, the minimum coins for amount n depends on minimum coins for n - coin[i]; those smaller amounts are reused. Another hint: the problem asks for "minimum," "maximum," "count," or "is it possible" over sequences, arrays, or grids. If you can write a recurrence and subproblems repeat, DP likely applies.

What is the difference between 0/1 knapsack and unbounded knapsack?

In 0/1 knapsack, each item can be used at most once. In unbounded knapsack, each item can be used any number of times. For 0/1, the recurrence is dp[w] = max(dp[w], dp[w - weight[i]] + value[i]) but you iterate items in an outer loop and process each once when filling the table, so you do not reuse the same item. For unbounded, you can loop over weights first and allow the same item to be considered again, or use a 1D DP array where dp[w] depends on dp[w - weight[i]] which may already include item i.

// 0/1 Knapsack - each item once
int Knapsack01(int[] w, int[] v, int cap) {
    var dp = new int[cap + 1];
    for (int i = 0; i < w.Length; i++)
        for (int j = cap; j >= w[i]; j--)
            dp[j] = Math.Max(dp[j], dp[j - w[i]] + v[i]);
    return dp[cap];
}

// Unbounded - iterate weights first so same item can repeat
int KnapsackUnbounded(int[] w, int[] v, int cap) {
    var dp = new int[cap + 1];
    for (int j = 1; j <= cap; j++)
        for (int i = 0; i < w.Length; i++)
            if (w[i] <= j)
                dp[j] = Math.Max(dp[j], dp[j - w[i]] + v[i]);
    return dp[cap];
}

How do I convert a recursive solution to a DP solution?

Write the recursive solution first. Identify the parameters that define a state (e.g., index and remaining amount). That becomes your DP state. The base cases become the initial table values. The recurrence (what the recursive function returns) becomes how you fill the table. For top-down, add a cache/memo to the recursive function. For bottom-up, determine the order to fill the table so that when computing dp[i][j], all dependencies (e.g., dp[i-1][j], dp[i][j-1]) are already computed.

Loading...

XLinkedInFacebook
Surya Singh

Surya Singh

Azure Solutions Architect & AI Engineer

Microsoft-certified Azure Solutions Architect with 8+ years in enterprise software, cloud architecture, and AI/ML deployment. I build production AI systems and write about what actually works—based on shipping code, not theory.

  • Microsoft Certified: Azure Solutions Architect Expert
  • Built 20+ production AI/ML pipelines on Azure
  • 8+ years in .NET, C#, and cloud-native architecture
LinkedInTwitter/XAbout Me