# Leetcode Perfect Squares problem solution

In this Leetcode Perfect Squares problem solution, we have given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

## Problem solution in Python.

```class Solution(object):
def numSquares(self, n):
from math import ceil, sqrt
dp = [0, 1, 2, 3]
if n<=3:
return dp[n]
else:
for i in range(4, n + 1):
dp.append(i)
for x in range(1, int(ceil(sqrt(i))) + 1):
temp = x*x
if temp>i:
break
else:
dp[i] = min(dp[i], 1 + dp[i - temp])
return dp[n]
```

## Problem solution in Java.

```class Solution {
public int numSquares(int n) {
int sqrtN = (int) Math.sqrt(n);
int[] squares = new int [sqrtN];
for (int i = 1; i <= sqrtN; i++) {
squares[i - 1] = i * i;
}
int[] dp = new int [n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = n + 1;
for (int j = 0; j < squares.length; j++) {
if (i < squares[j]) {
continue;
}
if (squares[j] == i) {
dp[i] = 1;
continue;
} else {
dp[i] = Math.min(dp[i], 1 + dp[i - squares[j]]);
}
}
}
return dp[n];
}
}
```

## Problem solution in C++.

```class Solution {
public:
int numSquares(int n)
{
if (n==0) return 0;
vector<int> per;
int f[n+5]={0};
f[1]=1;
for(int i=2;i<=n;i++)
{
int minV=INT_MAX;
int j=1;
while (j*j<=i)
{
if (j*j==i)
{
minV=1;break;
}
minV=min(minV,f[i-j*j]+1);
j++;
}
f[i]=minV;
}
return f[n];
}
};
```

## Problem solution in C.

```void solve(int n, int * ans, int a){
if (a > *ans) return;
if (n == 0) {
if (a < *ans) *ans = a;
return;
}

int z = 1;

while (z++) {
// Find the biggest perfect square that is less than n.
if (z*z > n) {
z = z-1;
break;
}
}

while (z > 0) {
// continue trying every perfect square less than that.
solve(n - z*z, ans, a+1);
if (a+2 >= *ans) break;
z = z-1;
}

return;
}

int numSquares(int n) {
int ans = INT_MAX;
solve(n, &ans, 0);
return ans;
}
```