Perfect Squares

题目来源
一道DP题，求一个数最少由几个平方数组成。我一开始用二维DP，
因为是个完全背包问题，所以需要注意每个数都是可以取多次的。
代码如下：

class Solution {
public:
    int numSquares(int n) {
        int l = sqrt(n);
        vector<int> squares(l+1);
        vector<vector<int>> dp(l+1, vector<int>(n+1, 0));
        for (int i=1; i<=l; i++) {
            squares[i] = i * i;
        }
        for (int i=1; i<=n; i++)
            dp[1][i] = i;
        for (int i=2; i<=l; i++)
            for (int j=1; j<=n; j++) {
                if (j >= squares[i])
                    dp[i][j] = min(dp[i-1][j], min(dp[i-1][j-squares[i]] + 1, dp[i][j-squares[i]] + 1));
                else
                    dp[i][j] = dp[i-1][j];
            }
        return dp[l][n];
    }
};

但是内存溢出了，所以需要改成一维DP。
代码如下：

class Solution {
public:
    int numSquares(int n) {
        int l = sqrt(n);
        vector<int> squares(l+1);
        vector<int> dp(n+1, 0);
        for (int i=1; i<=l; i++) {
            squares[i] = i * i;
        }
        for (int i=1; i<=n; i++)
            dp[i] = i;
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=l && squares[j] <= i; j++)
                dp[i] = min(dp[i], dp[i-squares[j]] + 1);
            }
        return dp[n];
    }
};

然后看了讨论区，发现了静态DP，时间瞬间降了好多，感觉很厉害的样子！
代码如下：

class Solution {
public:
    int numSquares(int n) {
        static vector<int> dp{0};
        while (dp.size() <= n) {
            int m = dp.size(), squares = INT_MAX;
            for (int i=1; i*i<=m; i++)
                squares = min(squares, dp[m-i*i] + 1);
            dp.push_back(squares);
        }
        return dp[n];
    }
};