###### tags: `leetcode` `medium` `Math` `Dynamic Programming` `Breadth-First Search`
# [279. Perfect Squares](https://leetcode.com/problems/perfect-squares/)

## Description

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.

## Examples
### 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 \leq n \leq 10^4$

## Code

#define MIN(x, y) x<y ? x : y

int numSquares(int n){
    int *result = malloc((n+1) * sizeof(int));
    int sqrt_bound = 0;
    for(int num = 0 ; num <= n ; num++){
        result[num] = num;
        sqrt_bound = sqrt(num);
        for(int remain_sqrt = 1 ; remain_sqrt <= sqrt_bound ; remain_sqrt++)
            result[num] = MIN(result[num], result[num-remain_sqrt*remain_sqrt] + 1);
    }
    
    return result[n];
}

## Complexity

|Space |Time |
|- |- |
|$O(N)$|$O(N^{3/2})$|

## Result

- Runtime: 126 ms, faster than 32.80%
- Memory Usage: 8.8 MB, less than 11.83%