Free Dynamic programming lessonsDynamic programming · Stage 11 · Mastery · Step 1

Fewest square tiles

The fewest perfect squares that add up to a number. About 12 minutes.

Is this a coin problem in disguise?

You need the fewest pieces from a fixed menu of sizes that add up to a target. You have met that shape before, in the coin change and knapsack stages. No coins are mentioned here, but the menu is the perfect squares: 1, 4, 9, 16 and so on.

So before you code, ask: what would the best answer for each smaller target be, and which of those does a target borrow from when it takes one more piece?

Fewest pieces to a total: think coins, and build from small totals.

Fewest perfect squares that add up to each number

012345678910111213

fewest

Zero needs no pieces. 1 is a square: 1 piece. 2 and 3 can only use 1s, so 2 and 3 pieces.

Move 1 of 5

Quick check

What is the fewest perfect squares that add up to 12?

Show the answer

3. 4 + 4 + 4 = 12.

Your problem

Fewest square tiles

You get a positive whole number n. Return the fewest perfect squares (1, 4, 9, 16, …) that add up to n. The same square may be used more than once.

Example

n = 12 → 3

1 ≤ n ≤ 10,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.