DP | Take/Not Take | Beginner Friendly | Memoization
Intuition\n Describe your first thoughts on how to solve this problem. \nDP - Memoization\n\n# Approach\n Describe your approach to solving the problem. \nWe us
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDP - Memoization\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe use the basic DP approach of take and not take, and return whenever our req target becomes 0 or return whenever our index goes out of bounds.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n*k)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O((k+1)*(n+1))$$\n\n\n# Code\n```\nclass Solution {\npublic:\n    int maxi = -1;\n    int n;\n    int solve(int reqk, int ind, vector<int> &nums, vector<vector<int>> &dp){\n        // base\n        if(reqk == 0){\n            return 0;\n        }\n        if(ind == n){\n            return -1e5;\n        }\n        if(dp[reqk][ind] != -1) return dp[reqk][ind];\n        // take\n        int take = -1e5;\n        if(reqk >= nums[ind]){\n            take = 1 + solve(reqk-nums[ind],ind+1,nums,dp);\n        }\n        //nottake\n        int nottake = solve(reqk,ind+1,nums,dp);\n        return dp[reqk][ind] = max(take,nottake);\n    }\n    int lengthOfLongestSubsequence(vector<int>& nums, int k) {\n        n= nums.size();\n        vector<vector<int>> dp(k+1,vector<int>(n+1,-1));\n        int ret = solve(k,0,nums,dp);\n        return ret > 0 ? ret : -1;\n    }\n};\n```\n## PLEASE DO UPVOTE IF YOU FIND THE SOLUTION HELPFUL! :)
['Dynamic Programming', 'Memoization', 'C++']