[leetcode] Perfect Squares

要利用好square的性质 不要逐个逐个地去brute force...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public class Solution { public int numSquares(int n) { if (n <= 0) return 0; if (n <= 3) return n; int lookup[] = new int[n+1]; lookup[1] = 1; lookup[2] = 2; for (int i = 3; i <= n; i++){ int temp = (int)Math.sqrt(i); if (temp*temp == i){ lookup[i] = 1; }else{ lookup[i] = Integer.MAX_VALUE; for (int j = 1; j*j <= i; j++){ lookup[i] = Math.min(lookup[i], lookup[i-j*j]+1); } } } return lookup[n]; } }