LeetCode 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.
 

解析：完美平方数，给定一个数值n，可以写成有多个数字平方和的形式，要求选择最少的数字。

动态规划的思路，我们用dp数组表示每个数字需要由多少个平方数组成，即dp[i]=j表示数字i需要j个完全平方数.
每一个数都由前面的某个数加上一个完全平方数构成，dp[i + sep] = dp[i] + 1，其中sep表示一个完全平方数，所以数字i+sep可以由数字i加上完全平方数sep构成，数字i需要dp[i]个完全平方数。所以dp[i + sep]需要dp[i]加1个完全平方数。我们用循环将数字i到n都和n以内的完全平方数字组合，得到dp[i]的解。定义长度为n+1的数组，dp[0]=0，返回的结果为dp[n]。

具体代码如下：

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

运行时间212ms。

优化：上面定义了一个长度为n+1的数组，然后在循环中更新数组。这里定义长度为1的数组，每次循环增加数值，一直到dp数组长度>n。采用静态数组，在多次循环调用时可以共享。代码如下

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

运行时间为4ms。

参考：

https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics)