My two cents

```
using namespace std;
int dfs(int n, vector<int> & dp) {
if(n == 0) return 0;
if(dp[n] != 0) return dp[n];
dp[n] = n;
for(int i = 1; i * i <= n; i++) {
dp[n] = min(dp[n], 1 + dfs(n - i * i, dp));
}
return dp[n];
}
```

This basically the same problem as “Coin Change”, where the set of perfect squares less than n are the coin values and n is the amount.