Here's the solution:
function numSquares(n)
dp := array of size (n + 1) filled with infinity
dp[0] := 0
for i from 1 to n
k := 1
while k × k ≤ i
square := k × k
dp[i] := min(dp[i], dp[i - square] + 1)
k := k + 1
return dp[n]
The outer loop runs times. The inner loop runs times for each . Total time complexity is .