Perfect Squares [LeetCode]

Problem Description

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.

Solutions

I. Dynamic Programming
This problem can be solved by dynamic programming. If we call dp is the array of least numbers of perfect square numbers for each integer from 1 to n, we have the following relation:
dp[n] = 1 + min (dp[n-i*i] for i from 1 to square root of n)
However, (as of 2015-09-09) I saw people complain that the dynamic programming solution got Time Limit Exception (TLE) with Python. Therefore, StefanPochmann, a member of LeetCode, solved the solution by using "Static" dynamic programming. That means the array dp is a static variable of the class Solution.
Dynamic Programming C++ Code

view plainprint?

1. int numSquares(int n) {  
2.     static vector<int> dp {0};  
3.     while (dp.size() <= n) {  
4.         int m = dp.size(), squares = INT_MAX;  
5.         for (int i=1; i*i<=m; ++i)  
6.             squares = min(squares, dp[m-i*i] + 1);  
7.         dp.push_back(squares);  
8.     }  
9.     return dp[n];  
10. }  

int numSquares(int n) {
    static vector<int> dp {0};
    while (dp.size() <= n) {
        int m = dp.size(), squares = INT_MAX;
        for (int i=1; i*i<=m; ++i)
            squares = min(squares, dp[m-i*i] + 1);
        dp.push_back(squares);
    }
    return dp[n];
}

Dynamic Programming C++ : Reverse for-loops inside out

view plainprint?

1. int numSquares(int n) {  
2.     static vector<int> dp {0};  
3.     int m = dp.size();  
4.     dp.resize(max(m, n+1), INT_MAX);  
5.     for (int i=1, i2; (i2 = i*i)<=n; ++i)  
6.         for (int j=max(m, i2); j<=n; ++j)  
7.             if (dp[j] > dp[j-i2] + 1)  
8.                 dp[j] = dp[j-i2] + 1;  
9.     return dp[n];  
10. }  

int numSquares(int n) {
    static vector<int> dp {0};
    int m = dp.size();
    dp.resize(max(m, n+1), INT_MAX);
    for (int i=1, i2; (i2 = i*i)<=n; ++i)
        for (int j=max(m, i2); j<=n; ++j)
            if (dp[j] > dp[j-i2] + 1)
                dp[j] = dp[j-i2] + 1;
    return dp[n];
}

Dynamic Programming Python Code

view plainprint?

1. class Solution(object):  
2.     _dp = [0]  
3.     def numSquares(self, n):  
4.         dp = self._dp  
5.         while len(dp) <= n:  
6.             dp += min(dp[-i*i] for i in range(1, int(len(dp)**0.5+1))) + 1,  
7.         return dp[n]  

class Solution(object):
    _dp = [0]
    def numSquares(self, n):
        dp = self._dp
        while len(dp) <= n:
            dp += min(dp[-i*i] for i in range(1, int(len(dp)**0.5+1))) + 1,
        return dp[n]

Dynamic Programming Ruby Code

view plainprint?

1. $dp = [0]  
2. def num_squares(n)  
3.   $dp << (1..$dp.size**0.5).map { |i| $dp[-i*i] }.min + 1 until $dp[n]  
4.   $dp[n]  
5. end  

$dp = [0]
def num_squares(n)
  $dp << (1..$dp.size**0.5).map { |i| $dp[-i*i] }.min + 1 until $dp[n]
  $dp[n]
end

However, in Python, if you test that code with test case 1,000,000, you will get the TLE error.
NOTE: I'm very happy that LeetCode now provides testing against custom input (From 2015-09-09). This feature I've seen in Hackerrank and wanted LeetCode to implemente it for quite a long time ago.

II. Breadth First Search

Picture 1: Graph of numbers 

In this problem, we define a graph where each number from 0 to n is a node. Two numbers p < q is connected if (q-p) is a perfect square.

So we can simply do a Breadth First Search from the node 0.

Below is the Python code that even can pass the custom test case of 1,000,000.

Breadth First Search Python Code

view plainprint?

1. class Solution(object):  
2.     _dp = [0]  
3.     def numSquares(self, n):  
4.         """ 
5.         :type n: int 
6.         :rtype: int 
7.         """  
8.          
9.         q1 = [0]  
10.         q2 = []  
11.         level = 0  
12.         visited = [False] * (n+1)  
13.         while True:  
14.             level += 1  
15.             for v in q1:  
16.                 i = 0  
17.                 while True:  
18.                     i += 1  
19.                     t = v + i * i  
20.                     if t == n: return level  
21.                     if t > n: break  
22.                     if visited[t]: continue  
23.                     q2.append(t)  
24.                     visited[t] = True  
25.             q1 = q2  
26.             q2 = []  
27.                   
28.         return 0  

class Solution(object):
    _dp = [0]
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
       
        q1 = [0]
        q2 = []
        level = 0
        visited = [False] * (n+1)
        while True:
            level += 1
            for v in q1:
                i = 0
                while True:
                    i += 1
                    t = v + i * i
                    if t == n: return level
                    if t > n: break
                    if visited[t]: continue
                    q2.append(t)
                    visited[t] = True
            q1 = q2
            q2 = []
                
        return 0

PS: For now, I do not have very much time to write the code in Java, C++, C#, Javacript or Ruby, so you are extremely welcome to post your solutions as a comment!