Coding

Dynamic Programming Coding Questions

Dynamic programming is a high-signal topic that separates strong candidates from great ones. These problems test your ability to identify overlapping subproblems and build optimal solutions bottom-up.

Practice with AI Feedback — Free AI Mock Interview

Sample Questions & Strong Answers

Climbing Stairs — how many ways to climb n stairs (1 or 2 steps at a time)?

It's Fibonacci: ways(n) = ways(n−1) + ways(n−2). Base cases: ways(1) = 1, ways(2) = 2. Space-optimized: track only last two values. Time O(n), Space O(1).

💡

Pro tip: This is the canonical DP warm-up. Know the recursive, memo, tabulation, and space-optimized versions. Amazon, Apple, Google.

House Robber — max money without robbing adjacent houses.

DP: rob[i] = max(rob[i−1], rob[i−2] + nums[i]). Space-optimize to two variables: prev2 and prev1. Time O(n), Space O(1).

💡

Pro tip: The recurrence captures the binary choice at each house: rob it (take prev2 + current) or skip it (take prev1). Amazon, Google.

Coin Change — minimum coins to make amount.

Bottom-up DP: dp[0] = 0, dp[i] = min(dp[i − coin] + 1) for each valid coin. Initialize dp[1..amount] = ∞. Return dp[amount] (−1 if still ∞). Time O(amount × coins), Space O(amount).

💡

Pro tip: Unbounded knapsack pattern — each coin can be used multiple times. Greedy doesn't work here (classic counterexample: coins [1,3,4], amount 6). Amazon, Google, Microsoft.

Longest Increasing Subsequence (LIS).

O(n²) DP: dp[i] = max(dp[j]+1 for j < i where nums[j] < nums[i]), min value 1. Answer: max(dp). O(n log n) approach: patience sorting with binary search (maintain 'tails' array). Time O(n log n), Space O(n).

💡

Pro tip: Know the O(n²) solution first, then optimize to O(n log n) using binary search on the tails array. Microsoft, Google, Amazon — medium.

Longest Common Subsequence (LCS).

2D DP: dp[i][j] = LCS of s1[0..i−1] and s2[0..j−1]. If s1[i−1] === s2[j−1]: dp[i][j] = dp[i−1][j−1]+1. Else: dp[i][j] = max(dp[i−1][j], dp[i][j−1]). Time O(m×n), Space O(m×n) or O(n) optimized.

💡

Pro tip: Space-optimize to O(n) using a rolling row — only need previous row to compute current. Amazon, Google — foundational DP.

Word Break — can a string be segmented into dictionary words?

DP: dp[i] = true if s[0..i−1] can be segmented. For each i, check all j < i: if dp[j] is true and s[j..i−1] is in wordSet, set dp[i] = true. Use a set for O(1) word lookup. Time O(n² × m) where m is word lookup cost, Space O(n).

💡

Pro tip: Precompute a set from wordDict. Try all split points — the bottleneck is the inner loop. Google, Amazon, Meta — medium.

Unique Paths — count paths in m×n grid from top-left to bottom-right.

DP: dp[i][j] = dp[i−1][j] + dp[i][j−1]. Base: first row and column = 1. Space-optimize: single 1D array, update in-place. Time O(m×n), Space O(n). Math solution: C(m+n−2, m−1) — choose which steps go right.

💡

Pro tip: Know both DP and combinatorics solutions. The combinatorics answer impresses interviewers. Amazon, Google, Microsoft.

Edit Distance — minimum operations (insert, delete, replace) to transform s to t.

DP: dp[i][j] = edit distance of s[0..i−1] to t[0..j−1]. If chars match: 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]). Time O(m×n), Space O(m×n) or O(n) optimized.

💡

Pro tip: Memorize the three operations in the recurrence: delete from s = dp[i−1][j], insert into s = dp[i][j−1], replace = dp[i−1][j−1]. Google, Amazon, Microsoft — hard.

Partition Equal Subset Sum — can array be split into two equal-sum subsets?

If total sum is odd, return false. Target = sum/2. 0/1 knapsack DP: dp[j] = can we make sum j using elements seen so far. Iterate nums, for each num iterate j from target down to num: dp[j] |= dp[j−num]. Time O(n×sum), Space O(sum).

💡

Pro tip: Iterate capacity backwards to prevent using same element twice (0/1 knapsack pattern). Amazon, Apple — medium.

Jump Game — can you reach the last index?

Greedy: track maxReach. For each index i, if i > maxReach return false. Update maxReach = max(maxReach, i + nums[i]). Return true if loop completes. Time O(n), Space O(1).

💡

Pro tip: The greedy approach is simpler than DP here — DP works but greedy is more elegant. Amazon, Meta, Google — medium.

Decode Ways — count ways to decode a digit string to letters (1='A'...26='Z').

DP: dp[i] = ways to decode s[0..i−1]. Single digit valid (1–9): dp[i] += dp[i−1]. Two digits valid (10–26): dp[i] += dp[i−2]. Handle '0' carefully — '0' alone is invalid. Time O(n), Space O(1) optimized.

💡

Pro tip: Edge cases trip people up: '0' alone is invalid, '00' is invalid, '30' is invalid (>26). Test these explicitly. Amazon, Meta — medium.

Minimum Path Sum — minimum sum path from top-left to bottom-right of grid.

DP in-place: for each cell, dp[i][j] = grid[i][j] + min(dp[i−1][j], dp[i][j−1]). Handle edge rows/columns (only one option). Return dp[m−1][n−1]. Time O(m×n), Space O(1) (modify grid in-place).

💡

Pro tip: Modifying the grid in-place achieves O(1) extra space — mention this optimization. Amazon, Google.

Expert tips

Identify the subproblem first: 'what is dp[i] representing?' Before writing any code, write the recurrence.

For 0/1 knapsack (each item used once), iterate capacity backwards. For unbounded knapsack (unlimited uses), iterate forwards.

Top-down (memoization) and bottom-up (tabulation) are both valid — interviewers care more about correctness than which style.

Space-optimize by observing how many previous rows/columns the recurrence actually accesses.

Dynamic Programming Coding Questions FAQ

Use DP when: 1) the problem asks for an optimal value (min/max/count), 2) you can break it into overlapping subproblems, 3) a naive recursive solution has repeated subproblems. Keywords that signal DP: 'minimum number of,' 'maximum sum,' 'number of ways,' 'is it possible to.'

1D linear DP (Fibonacci, House Robber), 2D grid DP (Unique Paths, Minimum Path Sum), string DP (LCS, Edit Distance), knapsack variants (0/1 and unbounded), interval DP (Merge Intervals, Burst Balloons), and tree DP (Diameter, Max Path Sum).

Top-down (memoization) is faster to write and easier to reason about — start with the recursive solution, add a cache. Bottom-up (tabulation) often achieves better constant factors and enables space optimization. In interviews: start with top-down for clarity, then offer to optimize to bottom-up if asked.

If dp[i][j] only depends on dp[i−1][...] (previous row), reduce to a 1D array. Update right-to-left for 0/1 knapsack, left-to-right for unbounded. If it also depends on dp[i][j−1] (same row earlier column), can still use 1D array updated left-to-right. Analyze dependencies before compressing.

Practice Dynamic Programming Coding Questions with real-time AI.

Stop reading sample answers and start practicing. Get personalized feedback on structure, delivery, and depth — every time.

Start Free Practice AI Mock Interview

Free plan available · No credit card needed · Cancel anytime