This is a DP problem, which I solve using 2D array in python.
The problem is the way I generate the 2D array.
Standard solution:
def getFloor(F, c, d):
if d == 0 or c == 0:
return 0
if c == 1:
return d
if F[c][d] == -1:
F[c][d] = getFloor(F, c, d-1) + getFloor(F, c-1, d-1) + 1
return F[c][d]
def getMaxFloor(c,d):
F = [[-1] * (d + 1) for i in range(c + 1)]
ans = getFloor(F, c, d)
return ans
print(getMaxFloor(3,4)) #prints 14
My code:
def getFloor(F, c, d):
if d == 0 or c == 0:
return 0
if c == 1:
return d
if F[c][d] == -1:
F[c][d] = getFloor(F, c, d-1) + getFloor(F, c-1, d-1) + 1
return F[c][d]
def getMaxFloor(c,d):
F = [[-1] * (d + 1)] * (c+1)
ans = getFloor(F, c, d)
return ans
print(getMaxFloor(3,4)) #prints 15, instead of the correct answer 14
I check both of the arrays F when both are initialized, which returns true. What's the problem?