题目浅析

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

  • 简单地说，就是给你一个整型数组，你可以删除其中元素，但不改变元素顺序的情况下，制造出一个严格递增子数组，求该子数组的最长长度

思路分享

  • 目前的 dp 无非两种思路：1. 选或不选；2. 枚举选哪个。选或不选形成的决策类似二叉树，而枚举选哪个会类似多叉树。前者很多时候划分为前 i 个元素的子问题，后者则是经常划分为以 i 下标为尾部的子问题。对于本题，可以分为以 i 下标为末尾的最长递增子序列长度。

  • 回到本题，首先尝试用记忆化回溯实现，如果采用思路一，那么在选择当前位的数字时，传递的过程中还需要报错前一个选择的数字下标（或者值），否则将无法保证选出来的序列严格递增；如果采用思路二，则是在枚举的循环内完成对不能满足严格递增情况的过滤，只要传递尾部下标即可。

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

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 记忆化递归
        # n = len(nums)
        # @cache
        # def dfs(index:int) -> int:
        #     res = 0
        #     for i in range(index):
        #         if nums[i] < nums[index]:
        #             res = max(res, dfs(i))
        #     return res +1

        # return max(dfs(i) for i in range(n))

        # 改为递推
        n = len(nums)
        f = [0] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    f[i] = max(f[j], f[i])
            f[i] += 1
        return max(f)