0

Consider the following code for computing the minimum number of perfect squares summing to n. What is the value of dp[4] after the outer loop iteration i = 4 completes?

easy🧾 Code Trace Q12 of Q15

Dynamic Programming: Knapsack - Perfect Squares

Consider the following code for computing the minimum number of perfect squares summing to n. What is the value of dp[4] after the outer loop iteration i = 4 completes?

A4

B1

C3

D2

Step-by-Step Solution

Solution:

Step 1: Trace dp[4] updates
For i=4, j iterates over 1 and 2 because 1*1=1 <=4 and 2*2=4 <=4. - For j=1: dp[4] = min(inf, 1 + dp[3]) = 1 + dp[3] - For j=2: dp[4] = min(previous, 1 + dp[0]) = min(previous, 1 + 0) = 1 Since dp[0] = 0, dp[4] becomes 1.
Step 2: Confirm dp[4] final value
dp[4] = 1 means 4 can be represented as one perfect square (2*2). This matches the expected minimal count.
Final Answer:
Option B -> Option B
Quick Check:
dp[4] = 1 for 4 = 2^2 [OK]

Quick Trick: dp[4] = 1 because 4 is a perfect square itself [OK]

Common Mistakes:

MISTAKES

Off-by-one errors in loop
Ignoring dp[0] base case

Trap Explanation:

PITFALL

Candidates often forget dp[0] = 0 or miscalculate dp[i - j*j], leading to wrong dp[4].

Interviewer Note:

CONTEXT

Tests ability to mentally execute DP code and handle base cases correctly.

Master "Perfect Squares" in Dynamic Programming: Knapsack

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Dynamic Programming: Knapsack Quizzes