Dynamic Programming Interview Questions: 10 Worked Answers for Beginners

Build interview-ready DP reasoning through ten beginner questions, exact traces, language-neutral pseudocode and clear complexity analysis.

KnowledgeGate Team

Exam prep & CS education

Updated 30 Oct 20266 min read
Dynamic Programming Interview Questions: 10 Worked Answers for Beginners

Interview-ready dynamic programming means naming the state, transition, base cases and evaluation order, then tracing values and deriving complexity. Climbing stairs, Fibonacci, House Robber and minimum coin change let you practise that sequence with exact states, traces and complexity. The language-neutral pseudocode can be translated into your preferred language while practising Placement Preparation & Coding.

1. Questions 1 and 2: What is dynamic programming, and when should you consider it?

Question 1: What is dynamic programming? Dynamic programming stores answers to reusable subproblems and combines them into larger answers. Explain the state, transition, base case, evaluation order, final answer location and complexity. DP is a method, not another name for recursion.

Question 2: How do you recognise a DP candidate? Look for repeated subproblems and a larger answer built from smaller answers. F(6) needs F(5) and F(4); the F(5) branch also needs F(4), so caching avoids rebuilding it. Merge sort's independent halves do not overlap.

Describe one state, list its choices, connect each choice to a smaller state, identify repetition, then check whether the state space fits the constraints. For graph shortest paths and subset-sum reachability, read Floyd-Warshall and Subset Sum Interview Questions: 10 Worked Answers. Use that earlier post for Floyd-Warshall and its full subset-sum trace. For state design, work through climbing stairs, Fibonacci, House Robber and coin change.

2. Question 3: Define the state and recurrence for climbing stairs

There are n = 5 stairs, and each move climbs 1 or 2 stairs. How many distinct step sequences reach stair 5?

Define ways[i] as the number of sequences that land exactly on stair i. Set ways[0] = 1 for the one empty way to stand at the start, and ways[1] = 1. For i >= 2, the last move came from i - 1 or i - 2:

Code
ways[0] = 1; ways[1] = 1
for i = 2 to n: ways[i] = ways[i - 1] + ways[i - 2]
return ways[n]

i

0

1

2

3

4

5

ways[i]

1

1

2

3

5

8

The calculations are ways[2] = 1 + 1 = 2, ways[3] = 2 + 1 = 3, ways[4] = 3 + 2 = 5 and ways[5] = 5 + 3 = 8. Return ways[5] = 8, not the sum of the array.

Climbing-stairs recurrence from states 0 through 5, showing ways values 1, 1, 2, 3, 5, 8 and the final calculation ways[5] = 5 + 3 = 8.

If a prompt defines n = 0 differently, agree on the contract. Here, ways[0] = 1 counts the direct two-step sequence in ways[2].

3. Questions 4 and 5: Memoisation, tabulation and space optimisation

Question 4: Memoisation or tabulation? Memoisation uses top-down recursion and a cache; tabulation evaluates states bottom-up. With F(0) = 0 and F(1) = 1, two-branch recursion for F(6) makes 25 calls but reaches only seven states, 0 through 6. Memoisation computes each once; tabulation fills [0, 1, 1, 2, 3, 5, 8]. Both take O(n) time, while memoisation needs a recursion stack.

Choose memoisation for a natural recurrence with sparse reachable states. Choose tabulation when all smaller states are needed and explicit order avoids recursion depth. The state and transition stay the same.

Question 5: Can Fibonacci use constant extra space? Start with prev2 = 0 and prev1 = 1. After i = 2, 3, 4, 5, 6, the rolling pairs are (1,1), (1,2), (2,3), (3,5) and (5,8). Compute cur = prev2 + prev1, then shift the pair. The result is 8, with O(n) time and O(1) extra space. DSA using Java offers structured practice with more DSA patterns.

4. Question 6: Derive and trace House Robber instead of guessing the recurrence

Houses contain [2, 7, 9, 3, 1]; adjacent houses cannot both be selected. Define best[i] as the maximum from indices 0 through i. Either skip house i and keep best[i-1], or take it and add value[i] to best[i-2]:

Code
best[i] = max(best[i - 1], best[i - 2] + value[i])

Use an empty-prefix value of 0.

index

value

take total

skip total

best

0

2

0+2=2

0

2

1

7

0+7=7

2

7

2

9

2+9=11

7

11

3

3

7+3=10

11

11

4

1

11+1=12

11

12

The answer is 12, realised by indices 0, 2, 4: 2 + 9 + 1 = 12.

House Robber trace for values [2, 7, 9, 3, 1], highlighting selected indices 0, 2, 4, best values 2, 7, 11, 11, 12, and total 12.

A rolling solution takes O(n) time and O(1) extra space. Retain decisions or the full best array to recover indices.

5. Questions 7 and 8: Minimum coin change, greedy failure and loop direction

Question 7: Find the minimum coins for coins = [1,3,4] and amount = 6. Let dp[a] be the minimum coins forming a. Set dp[0] = 0 and other entries to sentinel 7, or amount + 1.

Code
for a = 1 to amount:
    for each coin c where c <= a:
        dp[a] = min(dp[a], 1 + dp[a - c])
return -1 if dp[amount] = 7, otherwise dp[amount]

For amounts 0 through 6, the final row is [0,1,2,1,1,2,2]. Amount 1 gives 1; amount 2 gives 2; amount 3 compares 3 through coin 1 with 1 through coin 3. Amount 4 compares 2, 2 and 1 through coins 1, 3 and 4. Amount 5 reaches 2 as 4 + 1. At amount 6, coin 3 gives 1 + dp[3] = 2, representing 3 + 3. Greedy 4 + 1 + 1 uses three coins, so it loses. Time is O(kA) and space is O(A).

Question 8: Why can loop direction change the problem? In 0/1 reachability with one value [3] and target 6, ascending order sets sum 3 from sum 0, then wrongly sets sum 6 from that new sum 3, reusing the item. Descending order checks 6 before changing 3, so 6 stays false. With two items [3,3], the second descending pass correctly makes 6 true. Minimum coin change intentionally allows reuse.

6. Question 9: Derive complexity from the state space and check the constraints

Use time = number of states x work per state. Climbing stairs has n + 1 states with O(1) work each, giving O(n). House Robber has one state per house and two choices, also O(n). Coin change has A + 1 states checking up to k coins, giving O(kA).

This is pseudo-polynomial because it depends on the value of A, not only its bit length. With k = 20 and A = 10,000, at most about 200,000 state-coin checks are plausible. With A = 1,000,000,000, an amount-indexed array is impractical; revisit the constraints and structure.

Report auxiliary and recursion-stack space separately. A memoised two-parameter solution may need a full cache plus maximum call depth; tabulation avoids that stack.

7. Question 10: How should you explain, test and debug a DP answer in an interview?

Use this 45-second order: define the state, choices, transition, base cases and evaluation order; identify the returned cell, derive time and space, then trace a small input. Do not begin with memorised code.

Check exact boundaries. Climbing stairs gives 1 for n = 0 and 2 for n = 2 under this contract. House Robber gives 0 for [], 5 for [5] and 7 for [2,7]. Minimum coin change gives 0 for amount 0 and -1 for coins = [2], amount = 3. Fibonacci gives F(0) = 0, F(1) = 1 and F(6) = 8.

Audit these traps: an ambiguous state, missing empty base case, unfilled dependency, accidental item reuse, wrong returned cell, or complexity without a state count. Continue with DSA Interview Questions: 7 Patterns for Placements for broader patterns. Coding for Placements offers structured practice.