'Is returning an argument in base case a bad practice when implementing memoization?
What's the best way to memoize a longest increasing subsequence for example?
I believe I have a mistake in the memoization of this solution. The usual approach is to to return 0 and add 1 at each step Is passing in a modified length a bad approach for longest increasing subsequence?
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
def helper(nums, currIndex, currLen, prev, dp, sofar):
if currIndex == len(nums):
return currLen
if (prev, currLen) not in dp:
include = 0
if prev == -1 or nums[currIndex] > nums[prev]:
include = helper(nums, currIndex + 1, currLen +1, currIndex, dp,
sofar + [nums[currIndex]])
exclude = helper(nums, currIndex + 1, currLen, prev, dp, list(sofar))
dp[(prev, currLen)] = max(include, exclude)
return dp[(prev, currLen)]
dp = {}
return helper(nums, 0, 0, -1, dp, [])
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
