商城网站制作报价做羞羞的事网站

思路：01背包

这个背包问题很经典了，但是这里涉及到一个问题，就是我们转化问题的时候发现，这个背包需要正好装满才行。这里我们把长度作为价值，也就是说每一个数的价值都是1。

我们需要把dp初始化为全部为负数，除了下标为0的dp[0]=0，因为如果是正好装满，那么dp[0]这里必定是会被转移到的，所以需要赋值为0，代表在体积为0的情况下的最大价值。

如果说没有符合条件的，我们需要返回-1，其实我们初始化为了一个很小的数，所以需要max(-1,dp[target])

上代码：

class Solution {
public:int lengthOfLongestSubsequence(vector<int>& nums, int target) {int n=nums.size();vector<int>dp(target+1,-2e9);dp[0]=0;for(int i=0;i<n;i++){for(int j=target;j>=nums[i];j--){dp[j]=max(dp[j-nums[i]]+1,dp[j]);}}return max(-1,dp[target]);}
};