【题解 | 01背包】和为目标值的最长子序列的长度

本文主要是介绍【题解 | 01背包】和为目标值的最长子序列的长度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

力扣：2915. 和为目标值的最长子序列的长度

给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。

返回和为 target 的 nums 子序列中，子序列 长度的最大值 。如果不存在和为 target 的子序列，返回 -1 。

子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。

示例 1：

输入：nums = [1,2,3,4,5], target = 9
输出：3
解释：总共有 3 个子序列的和为 9 ：[4,5] ，[1,3,5] 和 [2,3,4] 。
最长的子序列是 [1,3,5] 和 [2,3,4] 。所以答案为 3 。

示例 2：

输入：nums = [4,1,3,2,1,5], target = 7
输出：4
解释：总共有 5 个子序列的和为 7 ：[4,3] ，[4,1,2] ，[4,2,1] ，[1,1,5] 和 [1,3,2,1] 。
最长子序列为 [1,3,2,1] 。所以答案为 4 。

示例 3：

输入：nums = [1,1,5,4,5], target = 3
输出：-1
解释：无法得到和为 3 的子序列。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
1 <= target <= 1000

解题

这道题可以使用动态规划和01背包的思想，并进行空间压缩，减少空间复杂度。

首先定义dp数组，其中dp[j]表示和为j的子序列的最大长度。初始时，除了dp[0]为0，其余的dp[j]都被设置为Integer.MIN_VALUE，表示不可能得到和为j的子序列。

然后，对于数组nums中的每一个数num，我们都尝试更新dp[j]，其中j的范围是[num, s]，s是当前所有数的和与target的较小值。对于每一个j，我们可以选择使用num或者不使用num：

如果我们使用num，那么dp[j]就等于dp[j - num] + 1
如果我们不使用num，那么dp[j]就保持不变。

我们选择这两者的较大值作为新的dp[j]。

最后，如果dp[target]大于0，我们返回dp[target]，否则我们返回-1，表示不存在和为target的子序列。

参考代码：

class Solution {public int lengthOfLongestSubsequence(List<Integer> nums, int target) {int[] dp = new int[target + 1];Arrays.fill(dp, Integer.MIN_VALUE);dp[0] = 0;int s = 0;for (int num : nums) {s = Math.min(s + num, target);for (int j = s; j >= num; j--) {dp[j] = Math.max(dp[j], dp[j - num] + 1);}}return dp[target] > 0 ? dp[target] : -1;}
}