P153 最少完全平方数分解

描述#

这个题目说的是，给你一个正整数 n，你要计算出它最少可以分解成多少个完全平方数的和。完全平方数指的是可以表示成某个整数的平方的数字，比如 1、4、9、16 等等。

比如说，给你的 n 等于 5。5 最少可以表示成 1 和 4 这两个完全平方数相加：
5 = 1 + 4
因此 5 最少可以分解成 2 个完全平方数的和。
再比如说，给你的 n 等于 12。它最少可以分解成 4 + 4 + 4：
12 = 4 + 4 + 4
因此 12 最少可以分解成 3 个完全平方数的和。

代码#

public class AlgoCasts {

  // Time: O(n ^ 3/2), Space: O(n)
  public int numSquaresDP(int n) {
    int[] d = new int[n+1];
    d[0] = 0;
    for (int i = 1; i <= n; ++i) {
      d[i] = i;
      for (int j = 1; j*j <= i; ++j)
        d[i] = Math.min(d[i], d[i - j*j] + 1);
    }
    return d[n];
  }

  // Math.sqrt 时间复杂度是 O(1)
  // 参考链接：https://stackoverflow.com/questions/35524072/worst-case-time-complexity-of-math-sqrt-in-java
  private boolean isSquare(int n) {
    int a = (int) Math.sqrt(n);
    return a*a == n;
  }

  // Time: O(n ^ 1/2), Space: O(1)
  public int numSquaresMath(int n) {
    if (isSquare(n)) return 1;
    for (int i = 1; i*i <= n; ++i)
      if (isSquare(n - i*i))
        return 2;
    while (n % 4 == 0) n /= 4;
    if (n % 8 != 7) return 3;
    return 4;
  }

}