the-minimum-number-of-squares-needed-to-sum-to-n

general
1

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?

2

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
    ans.append(tempAns)

for _ in range(input()):
    printIt(_,ans[input()])
3

@vijju123 can you help me please

4

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

5

can u give me the link @vijju123

6

https://code.google.com/codejam/contest/7254486/dashboard#s=a&a=3