## Algorithm

Problem Name: 279. Perfect Squares

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.

Example 1:

```Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
```

Example 2:

```Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
```

Constraints:

• `1 <= n <= 104`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int numSquares(int n) {
int i, j, k;
int *dp;

dp = malloc((n + 1) * sizeof(int));
//assert(dp);

dp[0] = 0;
for (i = 1; i  < = n; i ++) {
k = dp[i - 1] + 1;      // answer of preceeding number plus 1
j = 2;
while (i >= j * j) {    // after j ^ 2
if (k > dp[i - j * j] + 1) {
k = dp[i - j * j] + 1;
}
j ++;
}
dp[i] = k;
}

k = dp[n];
free(dp);

return k;
}
``````
Copy The Code &

Input

cmd
n = 12

Output

cmd
3

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int numSquares(int n) {
static vector<int>dp(1, 0);
for(int i = dp.size(); i  < = n; i++){
dp.push_back(INT_MAX);
for(int j = 1; j * j  < = i; j++)
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
return dp[n];
}
};
``````
Copy The Code &

Input

cmd
n = 12

Output

cmd
3

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1; i  < = n; i++) {
int min = Integer.MAX_VALUE;
for (int j = 1; i - j * j >= 0; j++) {
min = Math.min(min, dp[i - j * j] + 1);
}
dp[i] = min;
}
return dp[n];
}
}
``````
Copy The Code &

Input

cmd
n = 13

Output

cmd
2

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numSquares = function(n) {
const dp = new Array(n+1).fill(Number.MAX_VALUE)
dp[0] = 0
for(let i = 1; i  < = n; i++) {
let min = Number.MAX_VALUE
let j = 1
while(i - j*j >= 0) {
min = Math.min(min, dp[i-j*j] + 1)
++j
}
dp[i] = min
}
return dp[n]
};
``````
Copy The Code &

Input

cmd
n = 13

Output

cmd
2

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def numSquares(self, n):
q, move = {i ** 2 for i in range(1, int(n ** 0.5) + 1)}, 1
coins = set(q)
while q:
if n in q: return move
q = {sm + c for sm in q for c in coins} - q
move += 1
``````
Copy The Code &

Input

cmd
n = 12

Output

cmd
3

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0279_PerfectSquares
{
public int NumSquares(int n)
{
var dp = new int[n + 1];
dp[0] = 0;
for (int i = 1; i  < = n; i++)
{
int j = 1, min = int.MaxValue;
while (i - j * j >= 0)
{
min = Math.Min(min, dp[i - j * j]);
j++;
}
dp[i] = min + 1;
}

return dp[n];
}
}
}
``````
Copy The Code &

Input

cmd
n = 12

Output

cmd
3