An intuitive DP.
class Solution { public: int numSquares(int n) { vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for(int i = 0; i <= n; i ++) for(int j = 1; j * j <= n - i; j ++) dp[i + j * j] = min(dp[i + j * j], dp[i] + 1); return dp[n]; } };
原文：http://www.cnblogs.com/tonix/p/4802536.html