# 279. Perfect square

2021-06-20 06:42:11

Given a positive integer  n, Find some perfect squares （ such as  1, 4, 9, 16, ...） Make their sum equal to n. You need to minimize the number of complete squares that make up the sum .

Give you an integer n , Return and for n Of the complete square of Minimum quantity .

Complete square It's an integer , Its value is equal to the square of another integer ; let me put it another way , Its value is equal to the product of the self multiplication of an integer . for example ,1、4、9 and 16 They're all perfect squares , and 3 and 11 No .

Example  1：

Input ：n = 12
Output ：3
explain ：12 = 4 + 4 + 4
Example 2：

Input ：n = 13
Output ：2
explain ：13 = 4 + 9

Tips ：

1 <= n <= 104

``````class Solution {
public:
int numSquares(int n) {
// Unlimited backpack
int d[10001] = {0};
d[0]=1;
int a[101],m=1;
while(m*m<=n)
{
a[m-1] = m*m;
m++;
}
m--;
for(int i = 0 ; i<m;i++)
for(int j = a[i];j<=n;j++)
{
if(d[j-a[i]]>0)
{
if(d[j]>0)
d[j] = min(d[j],d[j-a[i]]+1);
else
d[j] = d[j-a[i]]+1;
}
}
return d[n]-1;
}
};``````

https://chowdera.com/2021/06/20210611212743285o.html