Solution uses DP and recursion.

```
# @param {Integer} n
# @return {Integer}
@min_to_num = {0 => 0}
@squares = []
def get_all_perfect_squares(n)
i = 1
while (i * i <= n)
@squares << (i * i)
@min_to_num[i * i] = 1
i += 1
end
end
def min_num_squares(n)
if (@min_to_num.key?(n))
return @min_to_num[n]
end
mins = []
for square in @squares do
if (square > n)
break
else
mins << (n / square) + min_num_squares(n % square)
end
end
@min_to_num[n] = mins.min
return @min_to_num[n]
end
def num_squares(n)
@squares = []
get_all_perfect_squares(n)
return min_num_squares(n)
end
```