Easy Step-Step Video Solution 🔥 || DP + Memo 🔥 || 0/1 Knapsack 🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nTry to think from 0/1 knapsack take & not take. By observing the constraints we can com
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTry to think from 0/1 knapsack **take & not take**. By observing the constraints we can come up with Dynamic Programming Solution\n\n# ***Detailed and easy Video Solution***\n\nhttps://youtu.be/dyeV3pVzioE\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe code defines a class, "Solution," which computes the length of the longest subsequence of an integer array "v" with a sum less than or equal to a target value "t." It uses dynamic programming with memoization to recursively calculate the length of the longest subsequence. The "solve" function handles the recursive calculations, while "lengthOfLongestSubsequence" initializes the memoization table and returns the computed result. If no valid subsequence is found, it returns -1. The code can be converted from C++ to Java and Python while maintaining the same functionality.\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```C++ []\nclass Solution {\npublic:\n    int dp[1001][1001];\n    int solve(int i,vector<int>&v,int t)\n    {   \n        if(t==0)\n            return 0;\n        if(t<0 || i>=v.size())\n            return INT_MIN;\n        if(dp[i][t]!=-1)\n            return dp[i][t];\n        int a=1+solve(i+1,v,t-v[i]);\n        int b=solve(i+1,v,t);\n        return dp[i][t]=max(a,b);\n    }\n    int lengthOfLongestSubsequence(vector<int>& v, int t) {\n        int n=v.size();\n        memset(dp,-1,sizeof(dp));\n        int ans=solve(0,v,t);\n        if(ans<=0)\n            return -1;\n        return ans;\n    }\n};\n```\n```python []\nclass Solution:\n    def __init__(self):\n        self.dp = []\n\n    def solve(self, i, v, t):\n        if t == 0:\n            return 0\n        if t < 0 or i >= len(v):\n            return float(\'-inf\')\n        if self.dp[i][t] != -1:\n            return self.dp[i][t]\n        a = 1 + self.solve(i + 1, v, t - v[i])\n        b = self.solve(i + 1, v, t)\n        self.dp[i][t] = max(a, b)\n        return self.dp[i][t]\n\n    def lengthOfLongestSubsequence(self, v, t):\n        n = len(v)\n        self.dp = [[-1] * (t + 1) for _ in range(n + 1)]\n        ans = self.solve(0, v, t)\n        if ans <= 0:\n            return -1\n        return ans\n```\n```java []\nimport java.util.Arrays;\n\nclass Solution {\n    int[][] dp;\n\n    public int solve(int i, int[] v, int t) {\n        if (t == 0)\n            return 0;\n        if (t < 0 || i >= v.length)\n            return Integer.MIN_VALUE;\n        if (dp[i][t] != -1)\n            return dp[i][t];\n        int a = 1 + solve(i + 1, v, t - v[i]);\n        int b = solve(i + 1, v, t);\n        return dp[i][t] = Math.max(a, b);\n    }\n\n    public int lengthOfLongestSubsequence(int[] v, int t) {\n        int n = v.length;\n        dp = new int[n + 1][t + 1];\n        for (int[] row : dp)\n            Arrays.fill(row, -1);\n        int ans = solve(0, v, t);\n        if (ans <= 0)\n            return -1;\n        return ans;\n    }\n}\n\n```\n\n# ***If you like the solution Please Upvote and subscribe to my youtube channel***\n*It Motivates me to record more videos*\n\n*Thank you* \uD83D\uDE00
['Dynamic Programming', 'Memoization', 'Python', 'C++', 'Java']