> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/dynamic-programming/279.-perfect-squares.md).

# 279. Perfect Squares

DP Solution

```java
class Solution {
    public int numSquares(int n) {
        // base case must be dp[0]=0 not dp[1]=1;
        // dp[0] = 0;
        // dp[i] = min(dp[i-x^2])+1; (x = 0,1,2,...sqrt)
        int[] memo = new int[n+1];   
        
        for (int i=1; i<=n; i++){
            // the result won't be larger than i
            int min = i-1;
            int sqrt = (int) Math.sqrt(i);
            for(int j=1; j<=sqrt; j++){
                min = memo[i-j*j]<min? memo[i-j*j]: min;
            }
            memo[i] = min+1;
        }
        return memo[n];
    }
}
```