Perfect Squares

▶

Steps

setup

Initialize dp array

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).

fill_cells

Start filling dp for i=2

Compute dp[2]. Consider perfect squares j*j ≤ 2: j=1 only (1*1=1).

💡 We try to find minimal perfect squares count for 2 by checking dp[2 - 1] + 1.

Line:

for i in range(1, n + 1):
    j = 1
    while j*j <= i:

💡 We will update dp[2] by considering dp[1] + 1.

fill_cells

Update dp[2] using square 1

Update dp[2] by comparing current dp[2] and 1 + dp[2 - 1] = 1 + dp[1] = 2. Update dp[2] to 2.

💡 This shows dp[2] can be formed by two 1's (1+1).

Line:

dp[i] = min(dp[i], 1 + dp[i - j*j])

💡 dp[2] = 2 means minimal perfect squares count for 2 is two 1's.

fill_cells

Start filling dp for i=3

Compute dp[3]. Consider perfect squares j*j ≤ 3: j=1 only.

💡 We try to find minimal count for 3 by checking dp[3 - 1] + 1.

Line:

for i in range(1, n + 1):
    j = 1
    while j*j <= i:

💡 We will update dp[3] by considering dp[2] + 1.

fill_cells

Update dp[3] using square 1

Update dp[3] by comparing current dp[3] and 1 + dp[3 - 1] = 1 + dp[2] = 3. Update dp[3] to 3.

💡 This shows dp[3] can be formed by three 1's.

Line:

dp[i] = min(dp[i], 1 + dp[i - j*j])

💡 dp[3] = 3 means minimal perfect squares count for 3 is three 1's.

fill_cells

Start filling dp for i=4

Compute dp[4]. Consider perfect squares j*j ≤ 4: j=1 and j=2 (1*1=1, 2*2=4).

💡 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.

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. Consider the following Python code implementing the space-optimized 0/1 Knapsack solution. What is the output when weights = [10, 20, 30], values = [60, 100, 120], and W = 50?

def knapsack_space_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
print(knapsack_space_optimized(weights, values, W))

easy

A. 240

B. 180

C. 160

D. 220

Solution

1. Step 1: Trace dp array updates for each item

   For item 0 (weight=10, value=60), dp[w] updated for w=50 down to 10, dp[10..50]=60. For item 1 (weight=20, value=100), dp[30]=max(dp[30], dp[10]+100)=160, dp[50]=max(dp[50], dp[30]+100)=220. For item 2 (weight=30, value=120), dp[50]=max(dp[50], dp[20]+120)=max(220, 160+120)=280 but dp[20] is 60, so dp[50]=max(220, 180)=220.

2. Step 2: Final dp[50] value

   The maximum value achievable with capacity 50 is 220.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual dp tracing confirms max value 220 [OK]

Hint: Trace dp updates backward to avoid overcounting [OK]

Common Mistakes:

• Forwards iteration over w causes overcounting items.

2. What is the time complexity of the space-optimized bottom-up DP solution for Last Stone Weight II, where n is the number of stones and sum is the total weight of all stones?

medium

A. O(n + sum)

B. O(n^2)

C. O(n * sum * log n)

D. O(n * sum)

Solution

1. Step 1: Identify loops in the code

   Outer loop runs n times (for each stone), inner loop runs up to half the total sum (sum/2).

2. Step 2: Calculate total operations

   Each iteration updates dp array, so total operations ≈ n * (sum/2) -> O(n * sum).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP complexity depends on n and sum, not n squared or log factors [OK]

Hint: DP loops over stones and sums -> O(n * sum) [OK]

Common Mistakes:

• Confusing n with sum leading to O(n^2)
• Assuming logarithmic factor due to sorting
• Ignoring that dp array size depends on sum

3. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the minimum subset sum difference problem, given an input array of size n and total sum S?

medium

A. O(S^2)

B. O(n^2)

C. O(n * S)

D. O(n * log S)

Solution

1. Step 1: Identify loops in the code

   Outer loop runs n times (for each element), inner loop runs up to total_sum S times.

2. Step 2: Calculate total complexity

   Time complexity is O(n * S) because each element updates dp array of size S.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP iterates over n elements and sums up to S [OK]

Hint: Time depends on n and total sum, not n squared [OK]

Common Mistakes:

• Confusing n with S or assuming quadratic n^2
• Ignoring dp array size impact

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

1. 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.

2. Step 2: Modify DP accordingly

   Iterating forwards from weight to half updates dp[w] using dp[w - weight] from the same iteration, enabling reuse.

3. Step 3: Why other options fail

   Backward iteration prevents reuse; greedy is incorrect; recursion without memoization is inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Forward iteration in inner loop enables unlimited stone reuse [OK]

Hint: Unbounded knapsack -> inner loop forwards [OK]

Common Mistakes:

• Using backward iteration causing no reuse
• Trying greedy which is incorrect
• Ignoring memoization leading to TLE

5. Suppose the problem is modified so that each element in the array can be used multiple times (unlimited reuse) to form k equal sum subsets. Which of the following modifications to the DP with bitmask tabulation approach correctly adapts to this change?

hard

A. Use backtracking with memoization on subsets but do not use bitmasking since reuse breaks subset uniqueness

B. Keep the same bitmask DP but allow setting dp[next_mask] multiple times without restriction

C. Replace bitmask DP with a classic unbounded knapsack DP that tracks sums without bitmasking

D. Modify the bitmask DP to reset dp states after each full subset sum is reached to allow reuse

Solution

1. Step 1: Understand reuse impact

   Allowing unlimited reuse breaks the uniqueness assumption of subsets represented by bitmasks.

2. Step 2: Identify suitable DP approach

   Classic unbounded knapsack DP tracks sums without bitmasking, correctly handling reuse.

3. Step 3: Evaluate other options

   Bitmask DP relies on unique element usage; modifying it without removing bitmasking leads to incorrect states.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Unbounded knapsack DP handles reuse correctly [OK]

Hint: Bitmask DP assumes unique usage; reuse needs unbounded knapsack DP [OK]

Common Mistakes:

• Trying to reuse bitmask DP without removing uniqueness assumption
• Ignoring that reuse breaks subset partitioning logic