1. 题意

给定一个数组，求和为target的子序列的最长长度。

和为目标值的最长子序列的长度

2. 题解

动态规划，01背包模板题。
对于前i个物品可以选或者不选。

令dp[i][j]为前i个物品，选出和为j的序列最大长度。

状态转移方程则为

$$dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+1)$$

2.1 二维

class Solution {
public:int lengthOfLongestSubsequence(vector<int>& nums, int target) {int dp[1000 + 1][1000 + 1];int INF = 0x3f3f3f3f;memset(dp, -INF, sizeof(dp));for (int i = 0; i < 1001; ++i)dp[i][0] = 0;// dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + 1);int sz = nums.size();for ( int i = 1; i <= sz; ++i ) {for ( int j = 1;j <= target; ++j) {dp[i][j] = dp[i - 1][j];if ( j >= nums[ i - 1])dp[i][j] = max(dp[i][j], dp[i - 1][j - nums[i - 1]] + 1);}}return dp[sz][target] > 0 ? dp[sz][target] : -1;}
};

2.2 空间优化

dp[i][j] 是由dp[i - 1][j - nums[i]]和dp[i - 1][j]决定的，那么我们可以通过逆序枚举j的值来将空间上的值降为一维。

j的枚举最大值，不应该超过PrefixSum(nums, i)。

class Solution {
public:int lengthOfLongestSubsequence(vector<int>& nums, int target) {int dp[1001];int INF = 0x3f3f3f3f;memset(dp, -INF, sizeof(dp));dp[0] = 0;int sz = nums.size();int s  = 0;for ( int i = 1; i <= sz; ++i) {s += nums[i - 1];s  = min(target, s);for ( int j = s; j >= nums[i - 1]; --j )dp[j] = max(dp[j], dp[j - nums[i - 1]] + 1);}return dp[ target ] > 0 ? dp[ target ] : -1;}
};