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: https://leetcode.com/problems/perfect-squares/discuss/71495/An-easy-understanding-DP-solution-in-Java

关于DP，这题的特点是 （by @mnmunknown）：

• 要凑出来一个和正好是 n 的选择组合；

• 能选的元素是固定数量的 perfect square (有的会超) ；

• 一个元素可以选多次；

说明这其实是个背包问题。

Mathematical

See [[[[[)

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)

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;
    }
}

Reference

https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics

https://mnmunknown.gitbooks.io/algorithm-notes/82ff0c_bei_bao_wen_ti.html