Perfect Squares - Implementation

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 $O(n)$ times. The inner loop runs $O(\sqrt{i})$ times for each $i$. Total time complexity is $O(n \sqrt{n})$.