279. Perfect Square

做题历程：

1. 2016/Oct/20本题做了不止一遍，本次依旧没有解出，

依旧没有解出这道题实在是太不应该了，按理说做了一遍之后，这道题就没有什么秘密可言了，基本就是一道Easy，再说一遍思路吧，这道题是用Dynamic Programming解决。。 递推公式也不难： dp[i] = (j From 1 to sqrt(i)) min(dp[i-j*j]+1)

上代码吧，代码如下所示：

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, 0);

        for (int i = 1; i <= n; ++i) {
            dp[i] = INT_MAX;
            for (int j = 1; j * j <= i; ++j) {
                dp[i] = min(dp[i], dp[i-j*j] + 1);
            }
        }
        return dp[n];
    }
};