动态规划 —— 0-1背包问题

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

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 。

class Solution {public int lengthOfLongestSubsequence(List<Integer> nums, int target) {/**0-1背包的问题：nums数组相当于物品；target相当于背包的容量每个元素只可以选取一次1. dp的含义：dp[i][j] 表示前i个元素中，和为j的子序列的长度的最大值   2. 状态转移方程：对每个元素nums[i] 两种情况：不选择：dp[i][j] = dp[i-1][j];选择：dp[i][j] = dp[i-1][j - nums[i]] + 1; (这里需要 j > nums[i]) 【可以把目标值代入】dp[i][j] = max(dp[i-1][j], (j>= nums[i]) ? dp[i-1][j-nums[i]] + 1 : 0)3. 初始化 dp[0][0] = 0; //前0个元素中和为0的子序列长度为0对于 j > 0，dp[0][j] = -1（或者一个特殊值表示无法达到该状态），因为仅一个元素 0 时无法组成非零和的子序列。4. 遍历顺序：从左到右最后结果为 dp[n][target]; 若dp[n][target] = -1;则说明达不到*/ // 创建一个数组 int[] dp = new int[target+1]; // 表示和为 j 的子序列长度的最大值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;}
}