[C++] 2D Dynamic Programming
Intuition\n Describe your first thoughts on how to solve this problem. \n- Use Dynamic Programming\n- Define dp[i][target] as the length of the longest subseque
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Use Dynamic Programming\n- Define `dp[i][target]` as the length of the longest subsequence starting from `i` that sums to the `target`\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Use the recursive version of dynamic programming with memoization\n- For each element, we can take or skip it, and choose the longer one\n\n# Complexity\n- Time complexity: $$O(n * target)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n * target)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    // time/space: O(n * target)/O(n * target)\n    int lengthOfLongestSubsequence(vector<int>& nums, int target) {\n        vector<vector<int>> dp(nums.size(), vector<int>(target + 1, INT_MIN));\n        int result = helper(nums, 0, target, dp);\n        if (result <= 0) return -1;\n        return result;\n    }\nprivate:\n    int helper(vector<int>& nums, int i, int target, vector<vector<int>>& dp) {\n        // terminate\n        if (target == 0) return 0;\n        if (target < 0) return INT_MIN;\n        if (i >= nums.size()) return INT_MIN;\n        if (dp[i][target] != INT_MIN) return dp[i][target];\n        \n        // enumerate\n        int take = 1 + helper(nums, i + 1, target - nums[i], dp);\n        int skip = helper(nums, i + 1, target, dp);\n        return dp[i][target] = max(take, skip);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C++']