先说一下怎么思考这个问题？
乍一看这个问题有点像子序列的DP问题，但是我发现如果以子序列的经验去解这道题，这个
优化就很难想出了，因为如果以第i个数为结尾子序列的最长长度为定义的话，那么我们需要从 前i - 1个转 移，时间复杂度就是O(N^2),并且我们还得记录以前i-1个状态的子序列的所有和，因为我们求的是一定要等于目标和，所以本题应该不是用子序列dp思想来做
那么说明类型的dp可以既能解决和的问题又能解决长度的问题
答案是背包DP
我们有一种背包问题的解法，恰好装满目标体积的最大最小值
那么根据经验我们就可以这么定义
从前i个物品当中选出体积恰好为目标和的最长长度
背包问题选或不选
//不选该物品，那么我们只用考虑前i - 1个物品
f[i][j] = f[i - 1][j]
//选该物品，那么我们需要从i - 1个物品当中选并且要预留出a[i]
f[i][j] = f[i - 1][j - a[i]] + 1;
状态转移方程
f[i][j] = max(f[i - 1][j],f[i - 1][j -a[i] + 1);
但是由于是恰好装满背包，那么我们在初始化的时候从定义出发
f[i][j]都为负无穷，-0x3f3f3f3f，那么就表示该状态是一个无效状态，也就是表示并不能恰好装满背包容量
初始化的时候我们从定义出发，f[0][0]表示，从前0个物品当中选出体积为0的最长长度
f[0][0] = 0
然后我们看看背包问题是怎么把体积和长度定死怎么更新的呢？
这是我们用图论的思想来画的，因为动态规划本质就是一个图
在求方案数的dp中，就可以借助画图来更好确定怎么搞
未优化版
class Solution { public: int lengthOfLongestSubsequence(vector<int>& nums, int target) { //背包问题， //从前i个物品当中选出体积恰好为target的最多物品个数 vector<vector<int>> f(1100,vector<int>(1100,-0x3f3f3f3f)); vector<int> a(nums.size() + 10,0); int n = nums.size(); for(int i = 0;i < n;i++) a[i + 1] = nums[i]; f[0][0] = 0; for(int i = 1;i <= n;i++) { for(int j = 0;j <= target;j++) { f[i][j] = f[i - 1][j]; if(j >= a[i]) { f[i][j] = max(f[i][j],f[i - 1][j - a[i]] + 1); } } } return max(-1,f[n][target]); } };
优化版
class Solution { public: int lengthOfLongestSubsequence(vector<int>& nums, int target) { //背包问题， //从前i个物品当中选出体积恰好为target的最多物品个数 vector<int> f(1100,-0x3f3f3f3f); vector<int> a(nums.size() + 10,0); int n = nums.size(); for(int i = 0;i < n;i++) a[i + 1] = nums[i]; f[0] = 0; for(int i = 1;i <= n;i++) { for(int j = target;j >= 0;j--) { if(j >= a[i]) { f[j] = max(f[j],f[j - a[i]] + 1); } } } return max(-1,f[target]); } };
我们看看如何优化，参考01背包优化
所以我们可以倒着枚举
