[leetcode] Perfect Squares

这题 我先从recursion入手... 把recursive case写出来(top to bottom) 然后再尝试 (Bottom to top)转成DP problem去解决
发现
f(n) = Math.min(f(k*k)+f(n-k*k)) if n is not a perfect square, k is the largest number < square root of n)
          1                                           if n is a perfect square

**有人用Lagrange's Four-Square Theorem 更快可以解决。

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

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