题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个数组和一个目标值，要从数组中找到和为目标值的最长子序列（子序列是从原数组可以删除一些值但不能改变顺序的子数组）

思路分享

  • 经典的 01 背包变式，思路就不做解析了，可看 【Leetcode Daily】416分割等和子集

  • 学到了，记忆化搜索的递归，可以通过函数的 cache_clear 方法去除，但最好还是不用罢

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        # 递推
        n = len(nums)
        # f = f(i-1, j) f(i-1, j-nums[i])+1
        f = [[-inf] * (target+1) for _ in range(n+1)]
        f[0][0] = 0
        for i, x in enumerate(nums):
            for j in range(target+1):
                if j < x:
                    f[i+1][j] = f[i][j]
                else:
                    f[i+1][j] = max(f[i][j], f[i][j-x] + 1)
        return f[n][-1] if f[n][-1] > 0 else -1

        # 记忆化搜索，容易爆内存
        # 在前 index+1 的元素中和为 cur 的情况
        # @cache
        # def dfs(index:int, cur:int) -> int:
        #     # if cur == 0:
        #     #     return 0
        #     if index < 0:
        #         return 0 if cur == 0 else -inf
        #     if nums[index] > cur:
        #         return dfs(index-1, cur)
        #     return max(dfs(index-1, cur), dfs(index-1, cur - nums[index])+1)
        # ans = dfs(len(nums)-1, target)
        # dfs.cache_clear()
        # return ans if  ans > 0 else -1