What is the main approach for solving the Length of the Longest Subsequence That Sums to Target problem?

The main approach involves using dynamic programming to track possible subsequence sums and their lengths. A state transition method is applied to update the longest subsequence for each sum.

How do dynamic programming and greedy approaches optimize this problem?

Dynamic programming helps in maintaining a table of subsequence sums, while the greedy approach ensures the longest subsequence is found by adding optimal elements. Both can be combined for more efficient solutions.

Why does the Length of the Longest Subsequence That Sums to Target problem use state transition?

State transition allows for tracking how subsequences evolve as you process each element, helping to efficiently find the longest subsequence that sums to the target value.

What happens if there is no valid subsequence in this problem?

If no subsequence sums to the target, the solution should return -1, indicating that it is not possible to achieve the target sum.

How can GhostInterview assist with dynamic programming problems like this one?

GhostInterview guides you through the process of building a dynamic programming solution, helping you understand state transitions and identify key optimizations for more efficient solutions.

#2915

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。返回和为 target 的 nums 子序列中，子序列长度的最大值。如果不存在和为 target 的子序列，返回 -1 。子序列指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。示例 …

数组动态规划

题目描述

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

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示前 $i$ 个数中选取若干个数，使得这若干个数的和恰好为 $j$ 的最长子序列的长度。初始时 $f[0][0]=0$ ，其余位置均为 $-\infty$ 。

对于 $f[i][j]$ ，我们考虑第 $i$ 个数 $x$ ，如果不选取 $x$ ，那么 $f[i][j]=f[i-1][j]$ ；如果选取 $x$ ，那么 $f[i][j]=f[i-1][j-x]+1$ ，其中 $j\ge x$ 。因此我们有状态转移方程：

f[i][j]=\max\{f[i-1][j],f[i-1][j-x]+1\}

最终答案为 $f[n][target]$ ，如果 $f[n][target]\le0$ ，则不存在和为 $target$ 的子序列，返回 $-1$ 。

时间复杂度 $O(n\times target)$ ，空间复杂度 $O(n\times target)$ 。其中 $n$ 为数组长度，而 $target$ 为目标值。

我们注意到 $f[i][j]$ 的状态只与 $f[i-1][\cdot]$ 有关，因此我们可以优化掉第一维，将空间复杂度优化到 $O(target)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        n = len(nums)
        f = [[-inf] * (target + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(nums, 1):
            for j in range(target + 1):
                f[i][j] = f[i - 1][j]
                if j >= x:
                    f[i][j] = max(f[i][j], f[i - 1][j - x] + 1)
        return -1 if f[n][target] <= 0 else f[n][target]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate explain the dynamic programming approach effectively?
question_mark
Do they recognize that backtracking is only used if DP doesn't yield the solution?
question_mark
Are they able to optimize the space complexity by using a greedy approach or a reduced state transition table?

warning

常见陷阱

外企场景

error
Failing to correctly handle edge cases where no subsequence exists that sums to the target.
error
Not understanding the necessity of updating the dynamic programming state in a way that ensures the subsequence is as long as possible.
error
Using brute-force methods instead of dynamic programming, leading to inefficient solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the target value is zero? The solution would need to handle the edge case where an empty subsequence is a valid answer.
arrow_right_alt
What if the input array is sorted? Could that lead to potential optimizations in the DP approach?
arrow_right_alt
How does this approach change if elements in nums can be negative?

help

常见问题

外企场景

继续练习

#2916 子数组不同元素数目的平方和 II #2919 使数组变美的最小增量运算数 #2920 收集所有金币可获得的最大积分