279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. 279. Perfect Squares 

---

本题问一个数n最少能由多少个完全平方数加和得到。 使用动态规划，设dp[i]表示数i最少能由多少个完全平方数加和得到，那么由i再加一个平方数j得到的数i+j*j可以由dp[i]+1个平方数组成。即递推公式为：
$$dp[i+j*j]=min(dp[i]+1)$$
具体实现时，我们是先求dp数组中前面的值dp[i]，然后不断缩小并更新dp[i+j*j]的结果。代码如下：

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; i + j * j <= n; ++j) {
                dp[i + j * j] = min(dp[i + j * j], dp[i] + 1);
            }
        }
        return dp[n];
    }
};

本代码提交AC，用时99MS。
这题还可以用纯数学的方法来解，涉及到四平方和定理，数学方法暂时就不研究了。

二刷，对于数i，其最大的平方数就是(sqrt(i))^2，所以从sqrt(i)到1都试一试，从哪个降下去的数目最少。对于第一个样例，sqrt(12)=3，所以依次尝试3,2,1，发现2降下去的数目最少，因为3降下去就是9+1+1+1，要4个数，比2降下去4+4+4多。

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

本代码提交AC，用时204MS。

三刷。转换为背包问题，先把所有可能的平方数求出来放到数组squares中，把每个平方数当做一件商品，限制背包容量为n，问最少拿多少件商品能填满背包。则对于每件商品，选择拿或者不拿。完整代码如下：

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

本代码提交AC，用时688MS。还可以进一步优化，dp数组可以变成一维的。