10.17

Algorithm (dynamic programming)
1. Let sq = [k²  |  1 ≤ k ≤ ⌊√n⌋] – all perfect squares ≤ n.
2. Create an array dp[0…n], initialise dp[0]=0 and the rest to +∞.
3. For i = 1 … n:
    for each s ∈ sq while s ≤ i:
        dp[i] = min(dp[i], 1 + dp[i-s]).
4. Output dp[n] – the minimum count of squares whose sum is n.

Pseudocode
sq = [k*k for k in 1..⌊√n⌋]
dp = [0] + [∞]*n
for i in 1..n:
  for s in sq where s ≤ i:
    dp[i] = min(dp[i], 1 + dp[i-s])
return dp[n]

Correctness sketch
dp[i] stores the optimum for every prefix 0…i; when considering s, we append that square to an optimal decomposition of i-s, guaranteeing optimality by induction.

Complexity
There are n outer iterations and ≤ √n inner iterations, so the running time is Θ(n √n).
The table uses Θ(n) space.

Back to Chapter 10