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 steps | State, transition, base case, order |
|---|---|
| Two styles | Top-down memoisation, bottom-up table |
| Typical gain | Exponential to polynomial time |
| Space trick | Keep 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
- Defining the state loosely, so transitions become unclear. Say exactly what dp[i] means.
- Wrong initial values, such as 0 for a minimisation instead of infinity.
- Off-by-one errors between dp indexes and string or array indexes.
- Using greedy where it fails, as with coin sets such as 1, 3 and 4.
- Forgetting that a rolling array needs the right iteration direction.
Dynamic Programming Interview Questions: questions with worked answers
1 Climbing stairs: ways to reach step n with 1 or 2 steps
easyThe 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.
pythondef climb(n): a, b = 1, 1 for _ in range(n - 1): a, b = b, a + b return b if n >= 1 else 1javalong 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 Minimum cost climbing stairs
easycost[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.
pythondef 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)javaint 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 House robber: maximum loot without robbing adjacent houses
mediumAt 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.
pythondef rob(nums): prev = cur = 0 for x in nums: prev, cur = cur, max(cur, prev + x) return curjavaint 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 House robber on a circle
mediumThe 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.
pythondef 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:]))javaint 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 Maximum subarray sum (Kadane)
mediumLet 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.
pythondef max_subarray(nums): cur = best = nums[0] for x in nums[1:]: cur = max(x, cur + x) best = max(best, cur) return bestjavaint 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 Maximum product subarray
mediumA 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.
pythondef 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 bestjavaint 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 Coin change: fewest coins for an amount
mediumdp[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.
pythondef 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 -1javaint 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 Coin change II: number of combinations
mediumCount 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).
pythondef 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]javaint 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 Decode ways: count the ways to decode a digit string
mediumdp[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.
pythondef 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 curjavaint 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 Word break: can a string be segmented into dictionary words?
mediumdp[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.
pythondef 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]javaboolean 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 Longest palindromic substring
hardExpand 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).
pythondef 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]]javaString 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 Best time to buy and sell stock with cooldown
hardModel 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.
pythondef 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)javaint 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
- Edit Distance and String DP Interview Questions
- Fast and slow pointers interview questions with solutions
- Fenwick Tree (Binary Indexed Tree) Interview Questions
- Graph Interview Questions and Answers
- Greedy algorithm interview questions with worked solutions
- Grid and Matrix DP Interview Questions
- Hashing interview questions with worked solutions
- Heap and Priority Queue Interview Questions
- Interval DP Interview Questions
- Interval interview questions with worked solutions
- Kadane algorithm interview questions with worked solutions
- KMP and string matching interview questions with solutions