Bottom up DP | Very easy | Pick - Not pick | Defining DP state, transitions, base case, final answer
DP State\ndp[i][j] --> max length subsequence when you consider elements uptill ith index and target to achieve is j\n\n# Transitions\ndp[i][j] = max(dp[i][j], 
# DP State\ndp[i][j] --> max length subsequence when you consider elements uptill ith index and target to achieve is j\n\n# Transitions\ndp[i][j] = max(dp[i][j], dp[i - 1][j]) \nMeans don\'t consider nums[i], so the next sub problem to search is dp[i - 1][j]\n\ndp[i][j] = max(dp[i][j], dp[i - 1][j - nums[i]])\nPicked nums[i], so next subproblem to consider is dp[i - 1][j - nums[i]] which means search uptill index i - 1 for target = j - nums[i]\n\n# Base Case\ndp[0][nums[0] = 1   (nums[0] target is achievable)\ninitialize non reachable states with very less value since a maximization problem\ndp[i][0] = 0    (for all i from 1 to n, target 0 is achievalbe by not doing anythong)\n\n# Final Answer \ndp[n - 1][target]   (if it is negative, return -1)\n\n# Complexity\n- Time complexity:\nO(n * 1000)\n\n- Space complexity:\nO(n * 1000)\n\n# Code\n```\nclass Solution {\npublic:\n    // dp[i][j] --> consider subsequence till i, with target = j\n    int lengthOfLongestSubsequence(vector<int>& nums, int target) \n    {\n        int n = nums.size();\n        int MX = max(target, *max_element(nums.begin(), nums.end())) + 1;\n        vector<vector<int>> dp(n, vector<int>(MX, -1e6));  \n        \n        dp[0][nums[0]] = 1;\n        for(int i = 0; i < n; i++) dp[i][0] = 0;\n        \n        for(int i = 1; i < n; i++)\n        {\n            for(int j = 0; j < MX; j++)\n            {\n                dp[i][j] = dp[i - 1][j];\n                if(j - nums[i] >= 0) \n                    dp[i][j] = max(dp[i][j], dp[i - 1][j - nums[i]] + 1);\n            }\n        }\n\n        return dp[n - 1][target] < 0 ? -1 : dp[n - 1][target];\n    }\n};\n```
['C++']