leetcode Question: Perfect Squares

Perfect Squares

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.

Analysis:

For this problem, I'd like to show the approach using BFS, and the DP. These methods is not very optimal since there is a mathematical soluiton can runs much faster. However, this problem also serves as a good practice for the BFS and DP.

The BFS approach considers finding the min numbers as a search problem. Specifically, the root node is the positive integer n, every time we subtract the value n with all the posiblle square values, which can be considered as a path from parent node to the child node. The goal is to find the shortest path, connect from root node to the node in which the value is zero. A simple way to reduce the computations is that: we could eliminate the node which we have seen before, since the path go through (if exists) the newly seen node, must not as short as any path that go through the previously seen node with same value.

The DP solution goes pretty straightforward, since for every value n, it must come from some value plus a square number. This can be written as:
d[n] = min(d[n - i * i] + 1), where d[n] is the least number of square numbers, and i * i <= n.

Code (C++) (BFS version):

class Solution {

public:

int numSquares(int n) {

queue<pair<int,int>> q;

map<int,bool> mp;

q.push(make_pair(n,1));

int val = 0;

int dep = 0;

while (!q.empty()){

val = q.front().first;

dep = q.front().second;

q.pop();

int i=1;

while (i*i <= val){i++;}

while (i>=1){

if (val-i*i == 0){

return dep;

}

if (mp.find(val-i*i)==mp.end()){

q.push(make_pair(val-i*i,dep+1));

mp[val-i*i] = true;

}

i--;

}

}

return dep;

}

};

Code (C++, DP version):

class Solution {

public:

int numSquares(int n) {

vector<int> res(n+1, INT_MAX);

res[0] = 0;

for (int i=0;i<=n; i++){

for (int j=1; j*j <= i; j++){

res[i] = min(res[i-j*j]+1, res[i]);

}

}

return res[n];

}

};

Code (Python, DP version):

class Solution(object):

def numSquares(self, n):

"""

:type n: int

:rtype: int

"""

res = [sys.maxint]*(n+1)

res[0] = 0

for i in range(1,n+1):

j = 1

while j*j <=i:

res[i] = min(res[i-j*j]+1, res[i])

j+=1

return res[n]