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

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

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

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

$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

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!