Easy Step-Step Solution 🔥 || DP + Memo 🔥 || 0/1 Knapsack 🔥
Intuition\nTry to think from 0/1 knapsack take & not take. By observing the constraints we can come up with Dynamic Programming Solution\n\n\n# Approach\nThe co
# Intuition\nTry to think from 0/1 knapsack take & not take. By observing the constraints we can come up with Dynamic Programming Solution\n\n\n# Approach\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:\n0(n*n)\n\n- Space complexity:\n0(n*n)\n\n# Code\n```\nclass Solution {\npublic:\n    int n;\n    int solve(int target, int ind, vector<int> &nums, vector<vector<int>> &dp){\n        // base\n        if(target == 0){\n            return 0;\n        }\n        if(ind == n){\n            return -1e5;\n        }\n        if(dp[target][ind] != -1) return dp[target][ind];\n        // take\n        int take = -1e5;\n        if(target >= nums[ind]){\n            take = 1 + solve(target-nums[ind],ind+1,nums,dp);\n        }\n        //nottake\n        int nottake = solve(target,ind+1,nums,dp);\n        return dp[target][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 ans = solve(k,0,nums,dp);\n        return ans > 0 ? ans : -1;\n    }\n};\n```
['C++']