I want to know how to solve the problem minimum area of squares which sum up to n

I am getting wrong answer

Can anyone explain this in detail

And can it be done without DP?

I want to know how to solve the problem minimum area of squares which sum up to n

I am getting wrong answer

Can anyone explain this in detail

And can it be done without DP?

You are getting wrong answer may be because of 12 because answer should be 3 -> 4+4+4 but may be you are getting 4 because of 9+1+1+1… Same Mistake I was doing in Google KickStart… hope this will help…

And yes… you can solve it using DP… just don’t be so greedy…

Here is solution…

```
def printIt(i,ans):
print "Case #" + str(i+1) + ":",ans
squares = [i*i for i in range(1,102)]
ans = [0,1]
for i in range(2,10001):
j = 0
tempAns = 1000000
while squares[j] <= i:
tempAns = min(tempAns,1+ans[i-squares[j]])
j += 1
ans.append(tempAns)
for _ in range(input()):
printIt(_,ans[input()])
```

Did you go through the editorial? Its second approach will hep you even if you dont know dp.