For example, if n is 10 then output is `2 (9+1)`

For example, if n is 13 then output is `2 (9+4)`

For example, if n is 12 then output is `3 (4+4+4)`

The problem is similar to coin exchange problem. Here we can start to find minimum number for sum of `1`

and continue till `n`

For example n = 4

```
int dp[] = new int[4]
```

dp[0] = 0. //

dp[1] = dp[1- (0*0)] + 1 = 1 //the +1 is having the current number in the list

dp[2] = dp[2 - (1*1)] + 1= 1+1 = 2

dp[3] = min of ( dp[3 - (1*1)] or dp[3 - (2*2)]) +1 //2*2 is > 3 so will be ignored

= min(dp[2]) + 1 = 3

dp[4] = min of (dp[4 - (1*1)] or dp[4 - (2*2)] or dp[4-(3*3)]) + 1

= min (dp[3], dp[0]) +1

= min(3,0)+1 = 1

The problem can be solved using **dynamic programming** where we start from calculating sum for 1 and work towards n.

```
public class Solution {
int squares(int n) {
int dp[] = new int[n+1];
dp[0] = 0
for (int i = 1;i&lbps;n;i++) {
int j =1;
while (i - (j*j) >= 0) {
dp[i] = Math.min(dp[i], dp[i-(j*j)]);
j++
}
}
return dp[n];
}
}
```