Perfect Squares — Min Squares Summing to N

DP

int numSquares(int n) {
  int[] dp = new int[n + 1];
  Arrays.fill(dp, Integer.MAX_VALUE);
  dp[0] = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j * j <= i; j++)
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
  return dp[n];
}

Lagrange 4-square theorem

Every positive integer is sum of ≤ 4 squares. Legendre's three-square theorem: 3 iff n ≠ 4^a(8b+7).

Math shortcut

Check if N is perfect square → 1. Else check Legendre form → 4. Else check sum of 2 squares → 2. Else 3. O(√N).

Applications

Number theory. Cryptographic protocols. Optimization problems.