I'm working on this Leetcode question. I cannot figure out the difference between my commented and uncommented code below. I'm returning an array at the base-case of a recursion, so when I call the dp(i, prev) function, the variable should hold the array with the two return values in it: length, number of occurrences (times).
Here's the code:
def findNumberOfLIS(self, nums: List[int]) -> int:
@lru_cache(None)
def dp(i, prev):
if i >= len(nums):
return [0, 1] # [length, num seqs]
if prev == -1 or nums[prev] < nums[i]:
# ****** HOW THE HECK IS THIS DIFFERENT FROM THE UNCOMMENTED CODE? ******
# takeLength, takeTime = dp(i + 1, i)
# takeLength += 1
# skipLength, skipTime = dp(i + 1, prev)
# if takeLength == skipLength:
# return [takeLength, takeTime + skipTime]
# elif skipLength > takeLength:
# return [skipLength, skipTime]
# else:
# return [takeLength, takeTime]
take = dp(i + 1, i)
take[0] += 1
skip = dp(i + 1, prev)
if take[0] == skip[0]:
return [take[0], take[1] + skip[1]]
elif skip[0] > take[0]:
return [skip[0], skip[1]]
else:
return [take[0], take[1]]
else:
return dp(i + 1, prev)
return dp(0, -1)[1]
Maybe I'm just exhausted, but I'm calling it quits. I even tried to have my wife, who knows nothing about programming, look at it (just to see if the two things reflected one another).
The commented-out code (takeLength, takeTime, skipLength, skipTime) works and passes most of the tests on Leetcode. I get a completely different answer with the code that isn't commented out (take/skip). I get a TLE with the working solution, but I spent the last two hours trying to figure out what I was doing wrong -- albeit, it's 3 AM, so I can barely type this.
Any ideas? Thank you!
It seems the problem with the 2nd (uncommented) code comes from using the cached mutable returns of dp, instead of unpacking them (which is the case in the 1st commented code). Making copies of these results solves the problem.
Another unmentioned problem is that dp is not reusable: the 1st time it's called, the return from dp(0, -1) will be cached and use in subsequent attempts (with different nums list); this can be solved by adding the numbers as a 3rd argument:
examples = [[1, 3, 5, 4, 7], [4,4,4,4,4,4]]
from functools import lru_cache
@lru_cache(None)
def dp(i, prev, nt):
if i >= len(nt):
return [0, 1] # [length, num seqs]
if prev == -1 or nt[prev] < nt[i]:
take = dp(i + 1, i, nt).copy() # the copy isn't really necessary
take[0] += 1
skip = dp(i + 1, prev, nt).copy() # neither this one
if take[0] == skip[0]:
return [take[0], take[1] + skip[1]]
elif skip[0] > take[0]:
return [skip[0], skip[1]]
else:
return [take[0], take[1]]
else:
return dp(i + 1, prev, nt).copy() # this copy is mandatory
for nums in examples:
print(dp(0,-1, tuple(nums)))
# [4, 2]
# [1, 6]
Note: actually making only a .copy() for the return is needed.