Create a dp array of size 13 (0 to 12) filled with infinity to represent unknown minimal counts. Set dp[0] = 0 as the base case since zero requires zero perfect squares.
💡 Initialization sets the foundation: dp[0] = 0 because no numbers are needed to sum to zero, and infinity elsewhere means those values are not computed yet.
Line:dp = [float('inf')] * (n + 1)
dp[0] = 0
💡 The base case dp[0] = 0 anchors the solution and allows building answers for all other numbers.
fill_cells
Start filling dp for i=1
Begin computing dp[1]. Consider perfect squares j*j ≤ 1. The only j is 1 (1*1=1).
💡 We try to build the minimal count for 1 by checking all perfect squares less than or equal to 1.
Line:for i in range(1, n + 1):
j = 1
while j*j <= i:
💡 We start from the smallest number and will update dp[1] by considering dp[1 - 1] + 1.
fill_cells
Update dp[1] using square 1
Update dp[1] by comparing current dp[1] and 1 + dp[1 - 1] = 1 + dp[0] = 1. Since dp[1] was infinity, update to 1.
💡 This step shows how dp[1] is improved by using one perfect square 1.
Line:dp[i] = min(dp[i], 1 + dp[i - j*j])
💡 dp[1] = 1 means 1 can be represented by one perfect square (1).
💡 We try to find minimal count for 4 by checking dp[4 - 1] + 1 and dp[4 - 4] + 1.
Line:for i in range(1, n + 1):
j = 1
while j*j <= i:
💡 We will update dp[4] by considering dp[3] + 1 and dp[0] + 1.
fill_cells
Update dp[4] using square 1
Update dp[4] by comparing current dp[4] and 1 + dp[4 - 1] = 1 + dp[3] = 4. Update dp[4] to 4.
💡 First, dp[4] is updated assuming one 1 plus dp[3].
Line:dp[i] = min(dp[i], 1 + dp[i - j*j])
💡 dp[4] can be at most 4 (four 1's).
fill_cells
Update dp[4] using square 4
Update dp[4] by comparing current dp[4] and 1 + dp[4 - 4] = 1 + dp[0] = 1. Update dp[4] to 1.
💡 Using the perfect square 4 itself gives a better minimal count for dp[4].
Line:dp[i] = min(dp[i], 1 + dp[i - j*j])
💡 dp[4] = 1 means 4 can be represented by one perfect square (4).
fill_cells
Fill dp for i=5 using squares 1 and 4
Compute dp[5]. Consider squares 1 and 4. First update dp[5] using square 1: dp[5] = min(∞, 1 + dp[4]) = 1 + 1 = 2.
💡 We try to build dp[5] by adding one square 1 to dp[4].
Line:dp[i] = min(dp[i], 1 + dp[i - j*j])
💡 dp[5] can be at most 2 using one 1 plus dp[4].
fill_cells
Update dp[5] using square 4
Update dp[5] by comparing current dp[5] and 1 + dp[5 - 4] = 1 + dp[1] = 2. dp[5] remains 2.
💡 Using square 4 plus dp[1] does not improve dp[5].
Line:dp[i] = min(dp[i], 1 + dp[i - j*j])
💡 dp[5] = 2 is minimal using either two 1's or one 4 plus one 1.
fill_cells
Fill dp for i=12 considering squares 1,4,9
Compute dp[12]. Consider squares 1, 4, and 9. First update dp[12] using square 1: dp[12] = min(∞, 1 + dp[11]). dp[11] is not yet computed, so dp[12] remains ∞.
💡 We start computing dp[12] by checking square 1 and dp[11].
Line:dp[i] = min(dp[i], 1 + dp[i - j*j])
💡 dp[12] cannot be updated using square 1 yet.
fill_cells
Update dp[12] using square 4
Update dp[12] by comparing current dp[12] and 1 + dp[12 - 4] = 1 + dp[8]. dp[8] = 2, so dp[12] = min(∞, 3) = 3.
💡 Using square 4 plus dp[8] gives dp[12] = 3.
Line:dp[i] = min(dp[i], 1 + dp[i - j*j])
💡 dp[12] can be formed by one 4 plus minimal count for 8.
fill_cells
Update dp[12] using square 9
Update dp[12] by comparing current dp[12] and 1 + dp[12 - 9] = 1 + dp[3] = 1 + 3 = 4. dp[12] remains 3.
💡 Using square 9 plus dp[3] does not improve dp[12].
Line:dp[i] = min(dp[i], 1 + dp[i - j*j])
💡 dp[12] = 3 is minimal using squares 4 and 8 combination.
reconstruct
Return final answer dp[12]
Return dp[12] which holds the minimal number of perfect squares that sum to 12, which is 3.
💡 The final dp array is fully computed, and dp[12] gives the answer.
Line:return dp[n]
💡 The minimal count for 12 is 3, confirming 12 = 4 + 4 + 4.
def numSquares(n):
dp = [float('inf')] * (n + 1) # STEP 1 initialize dp
dp[0] = 0 # STEP 1 base case
for i in range(1, n + 1): # STEP 2 start filling dp
j = 1
while j*j <= i: # STEP 2 iterate perfect squares
dp[i] = min(dp[i], 1 + dp[i - j*j]) # STEP 3 update dp[i]
j += 1
return dp[n] # STEP 16 return answer
if __name__ == '__main__':
print(numSquares(12)) # Output: 3
📊
Perfect Squares - Watch the Algorithm Execute, Step by Step
Watching the algorithm fill the dp array step-by-step reveals how subproblems build up to the final solution, making the logic of unbounded knapsack clear without needing to guess or infer from code alone.
Step 1/16
·Active fill★Answer cell
Item 0 - wt:0 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
dp[0] = 0 (base case)
Item 1 - wt:1 val:∞
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
Computing dp[1]
Item 1 - wt:1 val:1
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
dp[1] updated to 1
Item 2 - wt:2 val:∞
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
Computing dp[2]
Item 2 - wt:2 val:2
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
2
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
dp[2] updated to 2
Item 3 - wt:3 val:∞
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
2
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
Computing dp[3]
Item 3 - wt:3 val:3
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
2
3
∞
∞
∞
∞
∞
∞
∞
∞
∞
dp[3] updated to 3
Item 4 - wt:4 val:∞
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
2
3
∞
∞
∞
∞
∞
∞
∞
∞
∞
Computing dp[4]
Item 4 - wt:4 val:4
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
2
3
4
∞
∞
∞
∞
∞
∞
∞
∞
dp[4] updated to 4 (using 1)
Item 4 - wt:4 val:1
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
2
3
1
∞
∞
∞
∞
∞
∞
∞
∞
dp[4] updated to 1 (using 4)
Item 5 - wt:5 val:2
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
2
3
1
2
∞
∞
∞
∞
∞
∞
∞
dp[5] updated to 2 (using 1)
Item 5 - wt:5 val:2
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
2
3
1
2
∞
∞
∞
∞
∞
∞
∞
dp[5] finalized at 2
Item 12 - wt:12 val:∞
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
2
3
1
2
3
4
2
1
2
3
∞
Computing dp[12] using square 1
Item 12 - wt:12 val:3
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
2
3
1
2
3
4
2
1
2
3
3
dp[12] updated to 3 (using 4)
Item 12 - wt:12 val:3
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
2
3
1
2
3
4
2
1
2
3
3
dp[12] finalized at 3
Item 12 - wt:12 val:3
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
i=0
0
1
2
3
1
2
3
4
2
1
2
3
3
Answer dp[12] = 3
Key Takeaways
✓ The dp array builds up minimal counts from 0 to n by considering all perfect squares less than or equal to each number.
This insight is hard to see from code alone because the iterative updates and dependencies are implicit; visualization makes it explicit.
✓ Each dp[i] depends on previously computed dp[i - j*j], showing the unbounded knapsack pattern where items (perfect squares) can be used unlimited times.
Seeing the dependency arrows and updates clarifies how the solution reuses subproblems multiple times.
✓ The minimal count for dp[4] changes from 4 (using four 1's) to 1 (using one 4), illustrating how better perfect squares improve the solution.
This concrete example shows why checking all squares is necessary and how the algorithm finds optimal solutions.
Practice
(1/5)
1. You are given a list of positive integers and need to determine if it can be split into two subsets with equal sums. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Dynamic programming using a subset-sum style 0/1 knapsack approach to check for a subset with sum equal to half the total
B. Divide and conquer by recursively splitting the array into halves and checking sums
C. Sorting the array and using two pointers to find two subsets with equal sums
D. Greedy algorithm that picks the largest elements first until half the total sum is reached
Solution
Step 1: Understand the problem requires partitioning into two equal sum subsets
Since the problem asks if the array can be split into two subsets with equal sums, it reduces to finding a subset with sum equal to half the total sum.
Step 2: Identify the algorithm that checks subset sums efficiently
The 0/1 knapsack dynamic programming approach can determine if such a subset exists by building a DP table or array that tracks achievable sums up to half the total.
Final Answer:
Option A -> Option A
Quick Check:
Greedy and sorting approaches fail on many inputs; DP guarantees correctness [OK]
Hint: Partition reduces to subset sum with half total [OK]
Common Mistakes:
Thinking greedy or sorting solves partition optimally
2. Consider the following Python function implementing the Target Sum problem using bottom-up DP with offset indexing. What is the returned value when calling findTargetSumWays([1, 2], 1)?
easy
A. 1
B. 3
C. 0
D. 2
Solution
Step 1: Trace initial dp array
total=3, offset=3, dp=[0,0,0,1,0,0,0] (index 3 corresponds to sum 0)
Step 2: Process num=1 and num=2 updating dp
After num=1, dp counts ways to reach sums -1 and 1. After num=2, dp counts ways to reach sums -3,-1,1,3. dp[target+offset]=dp[1+3]=dp[4]=2.
Final Answer:
Option D -> Option D
Quick Check:
Two ways: +1-2 and -1+2 sum to 1 [OK]
Hint: Offset indexing maps sums to dp indices [OK]
Common Mistakes:
Off-by-one errors in indexing dp array
3. Examine the following code snippet which attempts to solve the problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.
medium
A. Line 7: zeros = s.count('0')
B. Line 10: for j in range(0, n - ones + 1):
C. Line 9: for i in range(0, m - zeros + 1): # iterating forwards
D. Line 11: dp[i + zeros][j + ones] = max(dp[i + zeros][j + ones], 1 + dp[i][j])
Solution
Step 1: Understand dp iteration direction
To avoid counting the same string multiple times, dp must be updated backwards (from high to low indices).
Step 2: Identify bug in iteration
Iterating forwards over i and j causes dp states to be reused within the same iteration, leading to overcounting.
Final Answer:
Option C -> Option C
Quick Check:
Backward iteration is required for 0/1 knapsack variants [OK]
4. Suppose the stones can be used multiple times (unlimited quantity of each stone). Which modification to the DP approach correctly computes the minimal last stone weight?
hard
A. Use a greedy approach smashing largest stones repeatedly
B. Keep the inner loop iterating backwards as in 0/1 knapsack to avoid reuse
C. Change the inner loop to iterate forwards from weight to half, allowing reuse of stones
D. Use recursion without memoization to explore all combinations with reuse
Solution
Step 1: Understand difference between 0/1 and unbounded knapsack
For unlimited reuse, inner loop must iterate forwards to allow multiple counts of the same stone.
Step 2: Modify DP accordingly
Iterating forwards from weight to half updates dp[w] using dp[w - weight] from the same iteration, enabling reuse.
Step 3: Why other options fail
Backward iteration prevents reuse; greedy is incorrect; recursion without memoization is inefficient.
Final Answer:
Option C -> Option C
Quick Check:
Forward iteration in inner loop enables unlimited stone reuse [OK]
5. Suppose the subset sum problem is modified so that each number can be chosen multiple times (unbounded). Which modification to the space-optimized DP code correctly solves this variant?
hard
A. Change the inner loop to iterate forwards from num to S, allowing reuse of the same number multiple times.
B. Keep the inner loop iterating backwards from S to num, as in the 0/1 subset sum problem.
C. Use a recursive brute force approach without memoization to handle multiple uses.
D. Sort the input array and apply a greedy approach picking largest numbers first.
Solution
Step 1: Understand difference between 0/1 and unbounded knapsack
In unbounded knapsack, items can be reused multiple times, so dp updates must allow reuse within the same iteration.
Step 2: Modify iteration direction
Iterating forwards allows dp[w] to use dp[w - num] updated in the same iteration, enabling multiple uses of num.
Step 3: Confirm correctness
Backward iteration prevents reuse in the same iteration, which is incorrect for unbounded variant.