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.
用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关于DP，这题的特点是 （by @mnmunknown）：
- 要凑出来一个和正好是 n 的选择组合；
- 能选的元素是固定数量的 perfect square (有的会超) ；
- 一个元素可以选多次；
说明这其实是个背包问题。
用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.
Dynamic Programming - Iterative Bottom Up (~ 22ms AC)
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
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)
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)
class Solution {
public int fun(Map<Integer,Integer> 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<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 1; i<= (int)Math.sqrt(n); i++)
{
map.put(i*i,1);
}
return fun(map,n);
}
BFS Version (~113ms 21.89%)
class Solution {
public int numSquares(int n) {
int numOfSquares = 0;
Queue<Integer> queue = new LinkedList<>();
Set<Integer> 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;
}
}
Last modified 2yr ago