題目如下

數(shù)據(jù)范圍

本題就是典型的背包問(wèn)題target就是容量，nums[i]就是第i個(gè)物品的重量。其實(shí)就是選最多的物品使得背包剛好裝滿。
令f(i,j)為當(dāng)考慮到i - 1物品時(shí)剛好裝到j(luò)重量的物品數(shù)。
當(dāng)j >= nums[j]時(shí) 有f(i,j) = max(f(i - 1,j - nums[i - 1]) + 1,f(i - 1,j))
當(dāng)j < nums[j]時(shí) 有f(i,j) = f(i - 1,j)
當(dāng)i >= 0 j == 0時(shí)有f(i,j) = 0
而i ==0 j > 0時(shí)顯然序列不存在 為了避免影響答案我們置為負(fù)無(wú)窮
所以我們可以寫(xiě)出代碼

通過(guò)代碼(未優(yōu)化)

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

當(dāng)然因?yàn)槊恳淮螌?duì)j的遍歷只需要用到上一行的數(shù)據(jù)所以我們只需要用一維數(shù)組倒序遍歷j即可(倒序是為了防止本應(yīng)該用到的舊數(shù)據(jù)被覆蓋)
利用滾動(dòng)數(shù)組優(yōu)化后移的代碼

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