[leetcode 279]Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example,
For example, given n =
Credits: Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
ACコード:
1, 4, 9, 16, ...
) which sum to n. For example, given n =
12
, return 3
because 12 = 4 + 4 + 4
; given n = 13
, return 2
because 13 = 4 + 9
. Credits: Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
ACコード:
class Solution
{
public:
int numSquares(int n)
{
int least[n+1];
memset(least,0,sizeof(least));
for(int i=1;i<=n;++i)
{
least[i]=i;
for(int j=1;j*j<=i;++j)
{
if(j*j==n)
least[i]=1;
else
least[i]=least[i-j*j]+1<least[i]?least[i-j*j]+1:least[i];
}
}
return least[n];
}
};