# 279. Perfect-Squares

difficulty: Medium

&#x20;section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }&#x20;

Given a positive integer n, find the least number of perfect square numbers (for example, `1, 4, 9, 16, ...`) which sum to n.

**Example 1:**

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

**Example 2:**

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

## Method One

```java
class Solution {
    public int numSquares(int n) {
        //  dp[n] 是以 n 为结尾的最少的个数。
        //  确实是个经典的 dp 套路
        //  复杂度是 N \sqrt{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;
            int j = 1;
            while( j*j <= i ) {
                min = Math.min( dp[ i - j*j ] + 1, min);
                j++;
            }
            dp[i] = min;
        }
        return dp[ n ];
    }
}
​
```
