### 题目

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.

### 第一层 - 朴素DFS

#### 代码

class Solution {
private Map<Integer,Integer> memo = new HashMap<>();
public int numSquares(int n) {
memo = new HashMap<>();
return dfs(n);
}
private int dfs(int remain) {
if (remain == 0) { return 0; }
Integer min = memo.get(remain);
if (min != null) { return min; }
min = Integer.MAX_VALUE;
for (int i = 1; i <= (int)Math.sqrt(remain); i++) {
min = Math.min(min,1+dfs(remain-i*i));
}
return min;
}
}


### 第二层 - 带备忘录的DFS（动态规划）

T(n) = min( T(n-11), T(n-22), T(n-3*3), … ) + 1

#### 代码

class Solution {
private Map<Integer,Integer> memo = new HashMap<>();
private int globalMin = Integer.MAX_VALUE;
public int numSquares(int n) {
globalMin = Integer.MAX_VALUE;
return dfs(n,n,0);
}
private Integer dfs(int orig, int remain, int count) {
if (remain == 0) { return 0; }                                  // base case
if (count == globalMin) { return null; }                        // 剪枝
Integer history = memo.get(remain);                             // 查表
if (history != null) { return history; }
Integer min = null;                                             // 递归
for (int i = (int)Math.sqrt(remain); i > 0; i--) {
Integer sub = dfs(orig,remain-i*i,count+1);
if (sub == null) { continue; }
min = (min == null)? sub+1 : Math.min(min,1+sub);
if (orig == remain) {                                       // 随时更新最小值
globalMin = Math.min(globalMin,min);
}
}
if (min != null) { memo.put(remain,min); }
return min;
}
}


### 第三层 - 标准自底向上的动态规划

#### 代码

class Solution {
public int numSquares(int n) {
if (n < 1) { return 0; }
int[] res = new int[n+1];
// base case 0->0, 1->1
res[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= Math.sqrt(i); j++) {
res[i] = (res[i] == 0)? res[i-j*j] + 1 : Math.min(res[i],res[i-j*j]+1);
}
}
return res[n];
}
}


#### 使用静态的备忘录，避免每次创建新的备忘录对象

class Solution {
private static int[] res = new int[16];
private static int cursor = 2;
{ res[1] = 1; }
public int numSquares(int n) {
if (n < 1) { return 0; }
if (cursor > n) { return res[n]; }                          // result exists
if (res.length < n+1) { res = Arrays.copyOf(res,n*2); }     // result array not long enough
for (int i = cursor; i <= n; i++,cursor++) {
for (int j = 1; j <= Math.sqrt(i); j++) {
res[i] = (res[i] == 0)? res[i-j*j] + 1 : Math.min(res[i],res[i-j*j]+1);
}
}
return res[n];
}
}


### 第四层 - 数学法Legendre Three Squares Theorem

#### 代码

class Solution {
public int numSquares(int n) {
// is 1?
if (isSquare(n)) { return 1; }
// is 4?
int copy = n;
while ((copy & 3) == 0) { // n % 4 = 0
copy >>= 2;
}
if ((copy & 7) == 7) { // n % 8 = 7
return 4;
}
// is 2?
for (int i = 1; i <= Math.sqrt(n); i++) {
if (isSquare(n-i*i)) { return 2; }
}
// is 3!
return 3;
}
private boolean isSquare(int n) {
int sqrt = (int)Math.sqrt(n);
return sqrt * sqrt == n;
}
}