Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. For example, given n = 12, ...
Given a positive integer n, find the least number of perfect square numbers (for example, 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
.
代碼如下:
1 public class Solution { 2 public int numSquares(int n) { 3 if(n<=2) 4 return n; 5 6 int min=n,t=0; 7 for(int i=2;i*i<=n;i++) 8 { 9 int c=i*i; 10 if(n%c==0) 11 t=n/c; 12 else 13 t=n/c+numSquares(n%c); 14 if(t<min) 15 min=t; 16 } 17 return min; 18 } 19 }