Well, after seeing the similar problems, you may have known how to solve this problem. Yeah, just to construct larger numbers from smaller numbers by adding perfect squares to them. shares a nice code and is rewritten below.

1 class Solution { 2 public: 3     int numSquares(int n) { 4         vector
     
       dp(n + 1); 5         iota(dp.begin(), dp.end(), 0); 6         int ub = sqrt(n), next; 7         for (int i = 0; i <= n; i++) { 8             for (int j = 1; j <= ub; j++) { 9                 next = i + j * j;10                 if (next > n) break;11                 dp[next] = min(dp[next], dp[i] + 1);12             }13         }14         return dp[n];15     }16 };
     

Well, you may have noticed that the above code has many repeated computations. For example, for n = 10 and 11, we will recompute dp[0] to dp[10]. So a way to reduce the running time is to use static variables to store those results and return it if it has already been computed. Stefan posts severl nice solutions .

Finally, the above strategy using static variables does not reduce the expected running time of the algorithm, which is still of O(n^(3/2)). And guess what? There exists a much faster O(n^(1/2)) algorithm using number theory, also posted by Stefan . I rewrite its clear C solution in C++ below (well, just a copy -_-).

1 class Solution { 2 public: 3     int numSquares(int n) { 4         while (!(n % 4)) n /= 4; 5         if (n % 8 == 7) return 4; 6         for (int a = 0; a * a <= n; a++) { 7             int b = sqrt(n - a * a); 8             if (a * a + b * b == n) 9                 return !!a + !!b;10         }11         return 3;12     }13 };