Take / Don't Take Recursion and DP - Python3
Intuition\nUsing take / don\'t take DP approach in Python 3. Need to cache / memoize to pass tests with this approach.\n\n# Approach\nGenerate subsequences recu
# Intuition\nUsing take / don\'t take DP approach in Python 3. Need to cache / memoize to pass tests with this approach.\n\n# Approach\nGenerate subsequences recursively, in each call try taking and not taking the current element, return the max of take / don\'t take. To avoid calling for the same i and target (j) over and over, cache the results in a dp array.\n\n# Code\n```\nclass Solution:\n    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n\n        # these are just impossible cases, so we can exit early                   \n        if sum(nums) < target:\n            return -1\n        if min(nums) > target:\n            return -1\n    \n        # trying to optimize, (saves about 1 sec on tests) - sort and remove\n        # numbers larger than target from nums. They are all positive so they\n        # won\'t be in the sub sequence\n        nums.sort()\n        nums = nums[0:bisect_right(nums, target)]\n        \n        # one more than max in description\n        max_allowed = 1001\n\n        n = len(nums)\n        \n        # dp[i][j] is the length of the sub seq ending on i\n        # that makes target j\n        dp = [[-max_allowed]*max_allowed for _ in range(n)]\n\n        \n        def sub_seq(i, new_target):\n            \n            # end - target is zero so we are done\n            if new_target == 0:\n                return 0\n    \n            # this means takeing the element was more than sum\n            if new_target < 0 or i >= n:\n                return -max_allowed\n            \n            # check if we have seen this before (how to find\n            # new_target ending at i element)\n            if dp[i][new_target] != -max_allowed:\n                return dp[i][new_target]\n            \n            # max length if we take i or don\'t take i\n            dont_take = sub_seq(i + 1, new_target)\n            take = sub_seq(i + 1, new_target - nums[i]) + 1\n\n            # save it to look up later\n            dp[i][new_target] = max(take, dont_take)\n            \n            return dp[i][new_target]\n    \n        ans = sub_seq(0, target) \n        \n        return ans if ans > -1 else -1\n\n```
['Python3']