Autocoder

Dynamic Programming Interview Questions

Last updated 2026-11-19

Dynamic programming solves a problem by breaking it into overlapping subproblems and storing each answer once. Interviewers love it because the same four steps decide every question: define the state, write the transition, set the base cases and decide the order of computation.

This page covers foundational one-dimensional DP problems from climbing stairs to stock states. Each has Python and Java code, complexity and edge cases. Specific families have their own pages: knapsack, grid DP, longest common subsequence and bitmask DP. For the recursion background see recursion interview questions.

Four stepsState, transition, base case, order
Two stylesTop-down memoisation, bottom-up table
Typical gainExponential to polynomial time
Space trickKeep only the last few rows or values

The pattern and when to spot it

Suspect DP when a question asks for the count, the maximum or minimum, or whether something is possible, and a brute-force recursion would revisit the same sub-problems. Typical wording: number of ways, minimum cost, longest, can it be formed. If decisions at one step only depend on a small summary of the past, that summary is your state.

Start by writing the recursion in words: what is the answer for the first i items, given the answers for fewer items? Add memoisation to remove repeated work, then convert to a bottom-up loop if you want to cut memory. When the transition looks back only one or two steps, replace the array by two variables. Counting combinations versus permutations in coin problems depends on loop order, so decide it consciously.

Mistakes that cost marks

Dynamic Programming Interview Questions: questions with worked answers

  1. 1

    Climbing stairs: ways to reach step n with 1 or 2 steps

    easy

    The last move into step i came from i-1 or i-2, so ways[i] = ways[i-1] + ways[i-2]. That is Fibonacci. Only the last two values are needed, so keep two variables instead of an array. Time O(n), space O(1). Edge cases: n equal to 0 or 1 (one way each), large n overflowing int (use long or a modulus), do not recurse without memoisation because it is exponential.

    python
    def climb(n):
        a, b = 1, 1
        for _ in range(n - 1):
            a, b = b, a + b
        return b if n >= 1 else 1
    java
    long climb(int n) {
        long a = 1, b = 1;
        for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }
        return b;
    }
  2. 2

    Minimum cost climbing stairs

    easy

    cost[i] is paid when you step on stair i, and you may start at 0 or 1 and jump past the top. Let best[i] be the cheapest way to stand on i: cost[i] + min(best[i-1], best[i-2]). The answer is min(best[n-1], best[n-2]). Two rolling variables suffice. Time O(n), space O(1). Edge cases: two stairs, equal costs, a very expensive last stair that is better skipped.

    python
    def min_cost(cost):
        a, b = cost[0], cost[1]
        for i in range(2, len(cost)):
            a, b = b, cost[i] + min(a, b)
        return min(a, b)
    java
    int minCost(int[] cost) {
        int a = cost[0], b = cost[1];
        for (int i = 2; i < cost.length; i++) { int c = cost[i] + Math.min(a, b); a = b; b = c; }
        return Math.min(a, b);
    }
  3. 3

    House robber: maximum loot without robbing adjacent houses

    medium

    At house i either skip it, keeping best[i-1], or rob it and add to best[i-2]. So best[i] = max(best[i-1], best[i-2] + nums[i]). Keep two rolling values. Time O(n), space O(1). Edge cases: empty array (0), a single house, all zeros, a greedy choice of larger neighbours can fail so DP is needed.

    python
    def rob(nums):
        prev = cur = 0
        for x in nums:
            prev, cur = cur, max(cur, prev + x)
        return cur
    java
    int rob(int[] nums) {
        int prev = 0, cur = 0;
        for (int x : nums) { int t = Math.max(cur, prev + x); prev = cur; cur = t; }
        return cur;
    }
  4. 4

    House robber on a circle

    medium

    The first and last houses are adjacent, so they cannot both be robbed. Solve the linear problem twice, once on houses 0..n-2 and once on 1..n-1, and take the larger. A single house must be handled separately. Time O(n), space O(1). Edge cases: n equal to 1 (return that house), n equal to 2, all values equal.

    python
    def rob_circle(nums):
        def line(a):
            prev = cur = 0
            for x in a:
                prev, cur = cur, max(cur, prev + x)
            return cur
        if len(nums) == 1:
            return nums[0]
        return max(line(nums[:-1]), line(nums[1:]))
    java
    int robCircle(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(line(nums, 0, nums.length - 2), line(nums, 1, nums.length - 1));
    }
    private int line(int[] a, int lo, int hi) {
        int prev = 0, cur = 0;
        for (int i = lo; i <= hi; i++) { int t = Math.max(cur, prev + a[i]); prev = cur; cur = t; }
        return cur;
    }
  5. 5

    Maximum subarray sum (Kadane)

    medium

    Let cur be the best sum of a subarray ending here: either extend the previous one or start fresh at this element. cur = max(x, cur + x). The answer is the largest cur seen. Initialise from the first element, not 0, so all-negative arrays work. Time O(n), space O(1). Edge cases: all negative numbers (largest element), single element, large positive sums needing long.

    python
    def max_subarray(nums):
        cur = best = nums[0]
        for x in nums[1:]:
            cur = max(x, cur + x)
            best = max(best, cur)
        return best
    java
    int maxSubarray(int[] nums) {
        int cur = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            best = Math.max(best, cur);
        }
        return best;
    }
  6. 6

    Maximum product subarray

    medium

    A negative number can turn the smallest product into the largest, so track both the maximum and the minimum product ending at each position. For each x, the new max and min are the max and min of x, max*x and min*x. The answer is the best max seen. Time O(n), space O(1). Edge cases: zeros reset the product, two negatives making a positive, a single negative element, overflow for long arrays.

    python
    def max_product(nums):
        hi = lo = best = nums[0]
        for x in nums[1:]:
            c = (x, hi * x, lo * x)
            hi, lo = max(c), min(c)
            best = max(best, hi)
        return best
    java
    int maxProduct(int[] nums) {
        int hi = nums[0], lo = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            int a = hi * x, b = lo * x;
            hi = Math.max(x, Math.max(a, b));
            lo = Math.min(x, Math.min(a, b));
            best = Math.max(best, hi);
        }
        return best;
    }
  7. 7

    Coin change: fewest coins for an amount

    medium

    dp[a] is the fewest coins making amount a. dp[0] = 0 and dp[a] = 1 + min(dp[a - c]) over coins c not exceeding a. Initialise others to infinity and report -1 if dp[amount] is still infinity. Greedy fails for coin sets such as 1, 3, 4 with amount 6. Time O(amount * coins), space O(amount). Edge cases: amount 0 (0), impossible amounts (-1), a coin larger than the amount, duplicate coins.

    python
    def coin_change(coins, amount):
        INF = amount + 1
        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
    java
    int coinChange(int[] coins, int amount) {
        int INF = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        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] == INF ? -1 : dp[amount];
    }
  8. 8

    Coin change II: number of combinations

    medium

    Count combinations, where order does not matter, by looping coins in the outer loop and amounts in the inner loop: dp[a] += dp[a - c]. Swapping the loops would count permutations instead, which is a different problem. Time O(amount * coins), space O(amount). Edge cases: amount 0 (one way, the empty set), no coin fits, result overflow (modulus or long).

    python
    def change(amount, coins):
        dp = [1] + [0] * amount
        for c in coins:
            for a in range(c, amount + 1):
                dp[a] += dp[a - c]
        return dp[amount]
    java
    int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int c : coins)
            for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
        return dp[amount];
    }
  9. 9

    Decode ways: count the ways to decode a digit string

    medium

    dp[i] is the ways to decode the first i characters. A single digit 1 to 9 adds dp[i-1], and a two-digit number 10 to 26 adds dp[i-2]. A zero can only be part of 10 or 20, so a standalone zero contributes nothing. Time O(n), space O(1) rolling or O(n). Edge cases: leading zero (0 ways), consecutive zeros, 100 (0 ways), 27 (one way, cannot be a pair), empty string.

    python
    def num_decodings(s):
        if not s or s[0] == '0':
            return 0
        prev, cur = 1, 1
        for i in range(1, len(s)):
            nxt = 0
            if s[i] != '0':
                nxt += cur
            if 10 <= int(s[i-1:i+1]) <= 26:
                nxt += prev
            prev, cur = cur, nxt
        return cur
    java
    int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int prev = 1, cur = 1;
        for (int i = 1; i < s.length(); i++) {
            int nxt = 0;
            if (s.charAt(i) != '0') nxt += cur;
            int two = Integer.parseInt(s.substring(i - 1, i + 1));
            if (two >= 10 && two <= 26) nxt += prev;
            prev = cur; cur = nxt;
        }
        return cur;
    }
  10. 10

    Word break: can a string be segmented into dictionary words?

    medium

    dp[i] is true if the first i characters can be segmented. dp[0] is true. For each i, look for a j before it with dp[j] true and s[j:i] in the dictionary. Put the dictionary in a set, and limit j to the longest word length to speed it up. Time O(n * L) set lookups with L the longest word, each costing O(L), space O(n). Edge cases: empty string (true), word reuse allowed, no valid split, words that overlap, where greedy longest-first matching can fail.

    python
    def word_break(s, words):
        ws = set(words)
        n = len(s)
        dp = [True] + [False] * n
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in ws:
                    dp[i] = True
                    break
        return dp[n]
    java
    boolean wordBreak(String s, List<String> words) {
        Set<String> ws = new HashSet<>(words);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < i; j++)
                if (dp[j] && ws.contains(s.substring(j, i))) { dp[i] = true; break; }
        return dp[n];
    }
  11. 11

    Longest palindromic substring

    hard

    Expand around every centre. There are 2n-1 centres (each character and each gap between two). For each, widen while both ends match, and record the longest. A table dp[i][j] works but uses O(n^2) memory; centre expansion uses O(1). Time O(n^2), space O(1). Edge cases: single character, all identical characters (the whole string), two-character palindromes at gaps, empty string. Manacher algorithm gives O(n).

    python
    def longest_palindrome(s):
        best = (0, 0)
        for c in range(len(s)):
            for l, r in ((c, c), (c, c + 1)):
                while l >= 0 and r < len(s) and s[l] == s[r]:
                    l -= 1; r += 1
                if r - l - 1 > best[1] - best[0]:
                    best = (l + 1, r)
        return s[best[0]:best[1]]
    java
    String longestPalindrome(String s) {
        int start = 0, end = 0;
        for (int c = 0; c < s.length(); c++) {
            for (int k = 0; k < 2; k++) {
                int l = c, r = c + k;
                while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
                if (r - l - 1 > end - start) { start = l + 1; end = r; }
            }
        }
        return s.substring(start, end);
    }
  12. 12

    Best time to buy and sell stock with cooldown

    hard

    Model states instead of days: hold (own a share), sold (just sold today) and rest (no share, free to buy). Transitions: hold = max(hold, rest - price), sold = hold_prev + price, rest = max(rest, sold_prev). The answer is max(sold, rest) at the end. After selling you must wait one day before buying. Time O(n), space O(1). Edge cases: empty or single price (0), strictly falling prices (0), cooldown preventing buying the day after a sale.

    python
    def max_profit(prices):
        hold, sold, rest = float('-inf'), 0, 0
        for p in prices:
            hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold)
        return max(sold, rest)
    java
    int maxProfit(int[] prices) {
        int hold = Integer.MIN_VALUE / 2, sold = 0, rest = 0;
        for (int p : prices) {
            int nh = Math.max(hold, rest - p), ns = hold + p, nr = Math.max(rest, sold);
            hold = nh; sold = ns; rest = nr;
        }
        return Math.max(sold, rest);
    }

Frequently asked questions

How do I know a problem needs dynamic programming?

Look for optimal substructure and overlapping subproblems: the best answer is built from best answers of smaller cases, and a naive recursion repeats calls with the same arguments.

What is the difference between memoisation and tabulation?

Memoisation is top-down recursion that caches results. Tabulation is bottom-up iteration that fills a table in dependency order. Both give the same complexity; tabulation avoids recursion limits.

How can I reduce the space used by a DP solution?

If dp[i] depends only on the previous row or the last few values, keep just those. One-dimensional rolling arrays and two-variable updates cut memory from O(n) or O(n * m) down.

How much DP is asked in coding rounds?

Medium difficulty 1D and 2D DP appears often in product company tests. The DSA coding round guide suggests how to split preparation time.

Related guides

More in DSA Interview Questions

See all in this section