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. This post shares a nice code and is rewritten below.
1 class Solution { 2 public: 3 int numSquares(int n) { 4 vector<int> 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 };
原文：http://www.cnblogs.com/jcliBlogger/p/4796240.html