当前位置:网站首页>279. Perfect square

279. Perfect square

2021-06-20 06:42:11 ai52learn

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;
    }
};

 

版权声明
本文为[ai52learn]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/06/20210611212743285o.html