# Perfect Squares \#math #dynamicprogramming Given a positive integer n, find the least number of perfect square numbers (for example,`1, 4, 9, 16, ...`) which sum to n. **Example 1:** ``` Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. ``` **Example 2:** ``` Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. ``` ## Analysis ### Dynamic Programming 用DP关键在于定义状态和找到转化关系。这里用dp\[i]代表对`i`的perfect squares count，转化关系并不是很直观: ``` dp[n] = Min{ dp[n - i*i] + 1 }, for n - i*i >=0 && i >= 1 ``` 具体推理如下： The most intuitive approach besides brute force would probably be dynamic programming, whether it's bottom up iteration or recursion with memoization, they all based on the recurrence relation: ``` dp[0] = 0 dp[1] = dp[0]+1 = 1 dp[2] = dp[1]+1 = 2 dp[3] = dp[2]+1 = 3 dp[4] = Min{ dp[4-1*1]+1, dp[4-2*2]+1 } = Min{ dp[3]+1, dp[0]+1 } = 1 dp[5] = Min{ dp[5-1*1]+1, dp[5-2*2]+1 } = Min{ dp[4]+1, dp[1]+1 } = 2 . . . dp[13] = Min{ dp[13-1*1]+1, dp[13-2*2]+1, dp[13-3*3]+1 } = Min{ dp[12]+1, dp[9]+1, dp[4]+1 } = 2 . . . dp[n] = Min{ dp[n - i*i] + 1 }, for n - i*i >=0 && i >= 1 ``` where `dp[n]` stands for the perfect squares count of the given `n` Source: 关于DP，这题的特点是 （by @mnmunknown）： * 要凑出来一个和正好是 n 的选择组合； * 能选的元素是固定数量的 perfect square (有的会超) ； * 一个元素可以选多次； 说明这其实是个背包问题。 ### Mathematical See \[\[\[\[\[[https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem)\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem))\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem)\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem)))\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem%29\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem%29%29\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem%29\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem%29%29%29)\\](https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)\)]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)\)\)]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)\)]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)\)\)\)/)) ### BFS 用BFS乍一看较难理解，其实在于问题转化： 把数字0, 1, ..., n看成一个图graph的节点node，节点i, j 连接的条件是 `j = i + (a perfect square number)` or `i = j + (a perfect square number)` 已知起始点`0`,和终点`n`，这样问题就转化为一个最短路径问题。故使用BFS。 > ``` > // Consider a graph which consists of number 0, 1,...,n as > // its nodes. Node j is connected to node i via an edge if > // and only if either j = i + (a perfect square number) or > // i = j + (a perfect square number). Starting from node 0, > // do the breadth-first search. If we reach node n at step > // m, then the least number of perfect square numbers which > // sum to n is m. Here since we have already obtained the > // perfect square numbers, we have actually finished the > // search at step 1. > ``` ## Solution Dynamic Programming - Iterative Bottom Up (\~ 22ms AC) ```java class Solution { public 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]; } } ``` DP another version ```java class Solution { public 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) { int min = Integer.MAX_VALUE; int j = 1; while(i - j*j >= 0) { min = Math.min(min, dp[i - j*j] + 1); j++; } dp[i] = min; } return dp[n]; } } ``` Mathematical - (1ms AC) ```java class Solution { // Based on Lagrange's Four Square theorem, there // are only 4 possible results: 1, 2, 3, 4. public int numSquares(int n) { // If n is a perfect square, return 1. if(is_square(n)) { return 1; } // The result is 4 if and only if n can be written in the // form of 4^k*(8*m + 7). Please refer to // Legendre's three-square theorem. while ((n & 3) == 0) // n%4 == 0 { n >>= 2; } if ((n & 7) == 7) // n%8 == 7 { return 4; } // Check whether 2 is the result. int sqrt_n = (int)(Math.sqrt(n)); for(int i = 1; i <= sqrt_n; i++) { if (is_square(n - i*i)) { return 2; } } return 3; } private boolean is_square(int num) { int sqrt_num = (int) Math.sqrt(num); return sqrt_num * sqrt_num == num; } } ``` Recursion Memoization (**NOT RECOMMENDED**) - (655ms AC 4.86% percentile) ```java class Solution { public int fun(Map map, int target) { if(map.containsKey(target)) return map.get(target); int temp = Integer.MAX_VALUE; for(int i = 1; i<= (int)Math.sqrt(target); i++) { temp = Math.min(temp, fun(map,target - i*i)+1); } map.put(target, temp); return temp; } public int numSquares(int n) { int nums = (int)Math.sqrt(n); Map map = new HashMap(); for(int i = 1; i<= (int)Math.sqrt(n); i++) { map.put(i*i,1); } return fun(map,n); } ``` BFS Version (\~113ms 21.89%) ```java class Solution { public int numSquares(int n) { int numOfSquares = 0; Queue queue = new LinkedList<>(); Set visited = new HashSet<>(); queue.add(0); visited.add(0); while (!queue.isEmpty()) { int size = queue.size(); numOfSquares++; while (size > 0) { int num = queue.poll(); for (int i = 1; i*i <= n; i++) { int x = num + i*i; if (x == n) { return numOfSquares; } if (x > n) { break; } if (!visited.contains(x)) { queue.offer(x); visited.add(x); } } size--; } } return numOfSquares; } } ``` ## Reference [https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics](https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-\(BFS-DP-static-DP-and-mathematics\)/)