Take and Non-Take DP Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nWe have given that we have to find out the longest subsequence with the given target. S
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe have given that we have to find out the longest subsequence with the given target. So we need to use the recursion.\nBut the given contraints are large so we need to use DP Solution.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst of all we need to find out the subsequence with the help of Take & Non-Take approach and store the maximum of the Take & Non-Take in DP.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(N * N)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(N * N)$$\n\n# Code\n```\nclass Solution {\npublic:\n    \n    int solve(vector<int>& nums, int target, int n, int& ans, vector<vector<int> >&dp)\n    {\n        if (target == 0)\n        {\n            return 0;\n        }\n        if (target < 0 or n >= nums.size())\n        {\n          return INT_MIN;\n        }\n        if (dp[n][target] != -1)\n        {\n            return dp[n][target];\n        }\n        int take = 0;\n        \n        take = 1 + solve(nums, target - nums[n], n + 1, ans, dp);    \n        int nontake = 0 + solve(nums, target, n + 1, ans, dp);\n        \n        dp[n][target] = max(take, nontake);\n        \n        return dp[n][target];\n    }\n    int lengthOfLongestSubsequence(vector<int>& nums, int target) {\n        \n        int n = nums.size();\n        if (n == 1)\n        {\n            if (nums[0] == target)\n            {\n                return 1;\n            }\n            return -1;\n        }\n        n = 0;\n        vector<vector<int> >dp(1001, vector<int>(1001, -1));\n        int ans = solve(nums, target, n, ans, dp);\n        if (ans <= 0)\n          return -1;\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C++']