1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include <vector>

class Solution {
public:
    int lengthOfLongestSubsequence(std::vector<int>& nums, int target) {
        std::vector<int> dp(target + 1, -1);
        dp[0] = 0;
        
        for (int num : nums) {
            for (int i = target; i >= num; --i) {
                if (dp[i - num] >= 0) {
                    dp[i] = std::max(dp[i - num] + 1, dp[i]);
                }
            }
        }
        
        return dp.back();
    }
};