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

标签: 数组 动态规划

难度: Medium

给你一个下标从 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

Submission

运行时间: 736 ms

内存: 16.1 MB

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        n, res = len(nums), -1
        """回溯+记忆化搜索"""
        # @cache
        # def dfs(i, target, length):
        #     nonlocal res
        #     if target == 0:
        #         res = max(res, length)
        #         return
        #     if i == n: return
        #     if nums[i] <= target:
        #         dfs(i + 1, target - nums[i], length + 1)
        #     dfs(i + 1, target, length)
        # dfs(0, target, 0)
        # return res
        """改成递推"""
        # dp = [[0] + [-n-1] * target for _ in range(n + 1)]
        # for i, num in enumerate(nums):
        #     for j in range(target + 1):
        #         if j >= num: dp[i + 1][j] = max(dp[i][j], dp[i][j - num] + 1)
        #         else: dp[i + 1][j] = dp[i][j]
        # return -1 if dp[n][target] <= 0 else dp[n][target]

        """空间优化"""
        # f = [0] + [-n-1] * target
        # for num in nums:
        #     for j in range(target, num - 1, -1):
        #         f[j] = max(f[j], f[j - num] + 1)
        # return -1 if f[-1] <= 0 else f[-1]

        """进一步优化: 枚举前两个数的时候, 只需要枚举到前两个数的和就可以了, 无需枚举到target"""
        f = [0] + [-n-1] * target
        s = 0
        for num in nums:
            s = min(s + num, target)
            for j in range(s, num - 1, -1):
                if f[j] < f[j - num] + 1: f[j] = f[j - num] + 1
        return f[-1] if f[-1] > 0 else -1

Explain

该题解采用了动态规划的思路来解决问题。首先定义一个一维数组 f，其中 f[j] 表示达到和为 j 的子序列的最大长度。遍历数组 nums 中的每个数 num，然后逆向更新数组 f。对于每个 num，逆向更新从 target 到 num 的值，以防止同一个元素被重复使用。这种方式确保了每次更新都是基于之前状态的最优解。最后，如果 f[target] 是正数，则表示存在和为 target 的子序列，返回其长度；否则，返回 -1 表示不存在这样的子序列。

时间复杂度: O(n*target)

空间复杂度: O(target)

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        n, res = len(nums), -1
        f = [0] + [-n-1] * target  # f[j] 表示达到和为 j 的子序列的最大长度，初始化为非常小的值
        s = 0  # 用于优化遍历的边界
        for num in nums:
            s = min(s + num, target)  # 更新当前所有数字和的边界
            for j in range(s, num - 1, -1):  # 逆序更新，防止重复使用同一个数字
                if f[j] < f[j - num] + 1:  # 只有在可以通过 num 更新 j 的情况下才进行更新
                    f[j] = f[j - num] + 1
        return f[-1] if f[-1] > 0 else -1  # 检查是否存在有效的子序列

Explore

在动态规划的解法中，数组f的每个元素f[j]代表构成和为j的最长子序列的长度。因此，f[0]=0表示和为0的最长子序列长度为0（即没有元素）。对于其他的f[j]（j>0），初始化为一个非常小的负数（-n-1）是为了表示在没有任何元素被加入时，构成一个正数和为j是不可能的。这种初始化确保只有在找到至少一个有效的子序列时，f[j]的值才会被更新为非负数，从而避免错误地返回不存在的子序列长度。

在动态规划中逆序更新数组f是为了确保每个元素在一轮更新中只被使用一次。如果采用顺序更新，比如从f[0]到f[target]，那么在更新f[j]时可能会重复使用同一元素，因为更新较小的j值可能影响到后面的j值的更新。逆序更新从f[target]到f[num]（num是当前考虑的元素）可以确保当更新f[j]时，使用到的f[j-num]还没有被这轮循环中的当前元素影响，从而正确地反映了不重复使用当前元素的情况。

变量s在代码中用于记录在当前阶段，数组nums中所有元素的和的最大可能值，但不超过target。这样，当更新动态规划数组f时，只需要考虑从num（当前元素）到s的范围，而不是从num到target的完整范围。这个优化减少了每次内循环的迭代次数，特别是当s远小于target时，可以显著提高效率。

如果nums数组中包含负数或零，当前的动态规划方法可能不会有效，因为它假设所有的数字都是正数，且只考虑累加和。负数的加入可能导致和减少，从而需要考虑更复杂的情况，比如和可能在增加和减少之间变化。为了处理包含负数和零的情况，可以采用更一般的动态规划方法，如使用二维数组f[i][j]，其中i代表考虑到第i个元素，j代表当前的和，f[i][j]表示是否可以通过前i个元素得到和为j的子序列。这种方法考虑了更多的情况，但也更为复杂和耗费资源。