思路: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]);}
};