Navigation

DSA interview 12 min read

Top Dynamic Programming Interview Questions with Solutions (C++, Java, JS, Python)

This page collects the dynamic programming (DP) interview questions that separate confident candidates from the rest. DP scares people, but every problem here follows the same recipe: define a state, write the recurrence, pick a base case, and fill a table. Each entry gives the problem, the approach, the complexity, and a full C++/Java/JavaScript/Python solution via the switcher. For the foundations, read dynamic programming introduction and memoization vs tabulation.

The DP recipe: (1) What is the smallest piece of state that describes a subproblem? (2) How does a bigger answer build from smaller ones (the recurrence)? (3) What are the trivial base cases? (4) In what order do you fill the table so dependencies come first? Answer those four and the code is mechanical.

1. Climbing Stairs

Question. You can climb 1 or 2 steps at a time. How many distinct ways to reach step n?

Approach. Ways to reach step n = ways to reach n-1 plus ways to reach n-2 — it is Fibonacci. Keep just the last two values instead of a full array.

Complexity. O(n) time, O(1) space.

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; }
    return b;
}

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; }
    return b;
}

function climbStairs(n) {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) { const c = a + b; a = b; b = c; }
  return b;
}

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

Walk through this and Fibonacci in detail on the Fibonacci & climbing stairs page.

2. House Robber

Question. Given house values in a row, find the maximum you can rob without robbing two adjacent houses.

Approach. At each house, either skip it (keep the best up to the previous house) or rob it (its value plus the best up to two houses back). Track those two rolling totals.

Complexity. O(n) time, O(1) space.

#include <vector>
#include <algorithm>

int rob(const std::vector<int>& nums) {
    int prev = 0, cur = 0;
    for (int x : nums) {
        int next = std::max(cur, prev + x);
        prev = cur;
        cur = next;
    }
    return cur;
}

int rob(int[] nums) {
    int prev = 0, cur = 0;
    for (int x : nums) {
        int next = Math.max(cur, prev + x);
        prev = cur;
        cur = next;
    }
    return cur;
}

function rob(nums) {
  let prev = 0, cur = 0;
  for (const x of nums) {
    const next = Math.max(cur, prev + x);
    prev = cur;
    cur = next;
  }
  return cur;
}

def rob(nums):
    prev = cur = 0
    for x in nums:
        prev, cur = cur, max(cur, prev + x)
    return cur

3. Coin Change

Question. Given coin denominations and a target amount, return the fewest coins that sum to it, or -1 if impossible. Each coin may be used unlimited times.

Approach. dp[a] = fewest coins for amount a. Build from 0 up: for each amount, try every coin and take 1 + dp[a - coin]. Seed unreachable amounts with a sentinel larger than any real answer.

Complexity. O(amount · coins) time, O(amount) space.

#include <vector>
#include <algorithm>

int coinChange(const std::vector<int>& coins, int amount) {
    std::vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = std::min(dp[a], dp[a - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

import java.util.Arrays;

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(amount + 1);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++)
    for (const c of coins)
      if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
  return dp[amount] > amount ? -1 : dp[amount];
}

def coin_change(coins, amount):
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    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] <= amount else -1

4. Longest Common Subsequence

Question. Find the length of the longest subsequence common to two strings (characters in order, not necessarily contiguous).

Approach. dp[i][j] = LCS of the first i characters of a and first j of b. If the characters match, extend the diagonal; otherwise take the better of dropping one character from either string.

Complexity. O(m · n) time, O(m · n) space.

#include <string>
#include <vector>
#include <algorithm>

int longestCommonSubsequence(const std::string& a, const std::string& b) {
    int m = a.size(), n = b.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = (a[i-1] == b[j-1]) ? dp[i-1][j-1] + 1
                                          : std::max(dp[i-1][j], dp[i][j-1]);
    return dp[m][n];
}

int longestCommonSubsequence(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = (a.charAt(i-1) == b.charAt(j-1)) ? dp[i-1][j-1] + 1
                                          : Math.max(dp[i-1][j], dp[i][j-1]);
    return dp[m][n];
}

function longestCommonSubsequence(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = a[i-1] === b[j-1] ? dp[i-1][j-1] + 1
                                   : Math.max(dp[i-1][j], dp[i][j-1]);
  return dp[m][n];
}

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

5. Longest Increasing Subsequence

Question. Find the length of the longest strictly increasing subsequence.

Approach. The clean O(n log n) method keeps a tails array where tails[k] is the smallest possible tail of an increasing subsequence of length k+1. For each value, binary-search for the first tail ≥ it and overwrite it (or append). The length of tails is the answer.

Complexity. O(n log n) time, O(n) space.

#include <vector>
#include <algorithm>

int lengthOfLIS(const std::vector<int>& nums) {
    std::vector<int> tails;
    for (int x : nums) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return (int)tails.size();
}

import java.util.*;

int lengthOfLIS(int[] nums) {
    List<Integer> tails = new ArrayList<>();
    for (int x : nums) {
        int i = Collections.binarySearch(tails, x);
        if (i < 0) i = -(i + 1);          // insertion point
        if (i == tails.size()) tails.add(x);
        else tails.set(i, x);
    }
    return tails.size();
}

function lengthOfLIS(nums) {
  const tails = [];
  for (const x of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    if (lo === tails.length) tails.push(x);
    else tails[lo] = x;
  }
  return tails.length;
}

import bisect

def length_of_lis(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

See the longest increasing subsequence page for the simpler O(n²) version too.

6. 0/1 Knapsack

Question. Given item weights and values and a capacity W, maximize total value without exceeding W. Each item is taken at most once.

Approach. dp[w] = best value achievable with capacity w. Process items one at a time; for each item iterate capacities downward so each item is counted at most once (the 0/1 constraint).

Complexity. O(items · W) time, O(W) space.

#include <vector>
#include <algorithm>

int knapsack(const std::vector<int>& weights, const std::vector<int>& values, int W) {
    std::vector<int> dp(W + 1, 0);
    for (int i = 0; i < (int)weights.size(); i++)
        for (int w = W; w >= weights[i]; w--)
            dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
    return dp[W];
}

int knapsack(int[] weights, int[] values, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < weights.length; i++)
        for (int w = W; w >= weights[i]; w--)
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    return dp[W];
}

function knapsack(weights, values, W) {
  const dp = new Array(W + 1).fill(0);
  for (let i = 0; i < weights.length; i++)
    for (let w = W; w >= weights[i]; w--)
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
  return dp[W];
}

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

Full derivation on the 0/1 knapsack page.

7. Edit Distance

Question. Find the minimum number of single-character insertions, deletions, or replacements to turn string a into string b.

Approach. dp[i][j] = edit distance between the first i characters of a and first j of b. If the current characters match, carry the diagonal; otherwise it is 1 + min(delete, insert, replace). The base cases are turning a prefix into the empty string.

Complexity. O(m · n) time, O(m · n) space.

#include <string>
#include <vector>
#include <algorithm>

int minDistance(const std::string& a, const std::string& b) {
    int m = a.size(), n = b.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = 1 + std::min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
        }
    return dp[m][n];
}

int minDistance(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i-1) == b.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
        }
    return dp[m][n];
}

function minDistance(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++) {
      if (a[i-1] === b[j-1]) dp[i][j] = dp[i-1][j-1];
      else dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
    }
  return dp[m][n];
}

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

Pitfall: The classic 0/1 knapsack bug is iterating capacity upward in the 1D version — that lets an item be reused (it solves the unbounded knapsack instead). Iterate capacity downward to enforce “use each item once.”

Keep practicing

You now have templates for the two big DP families: 1D sequence DP (climbing stairs, house robber, coin change, LIS) and 2D string/grid DP (LCS, edit distance, knapsack). Drill more on the dynamic programming exercises, and study reusable shapes on the dynamic programming patterns page. Finish the interview track with behavioral & system-design basics.