Salar
BAN USERthis is much faster than a simple dynamic programming approach.
for example, for n=12:
I take 9 out and try to calculate 3 -> 2 - > 1
next I take 4 out and try to calculate 8->4 done.
my map is much smaller and I only calculate leastSquares for the numbers I need for the answer.
int leastSquares_helper(int n, int max, unordered_map<int, int>* myMap) {
unordered_map<int,int>::const_iterator got = myMap->find(n);
if(got != myMap->end()) {
return got->second;
}
int largest = (int)sqrt(n);
if((largest * largest) == n) {
myMap->insert(pair<int,int>(n, 1));
return 1;
}
if(largest > max) {
largest = max;
}
int best = INT_MAX;
while ((largest * largest) > (n/best)) {
best = min(leastSquares_helper(n - (largest * largest), largest, myMap) + 1, best);
largest--;
}
myMap->insert(pair<int,int>(n, best));
return best;
}
int leastSquares(int n) {
unordered_map<int, int>* myMap = new unordered_map<int, int>;
return leastSquares_helper(n, INT_MAX, myMap);
}
int main(){
cout<<leastSquares(12);
getchar();
return 0;
}
- Salar March 12, 2015
- Salar May 14, 2017