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… :wink:

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

for _ in range(input()):

@vijju123 can you help me please

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

can u give me the link @vijju123