动态规划之最长递增子序列

痛定思痛。 2023-09-30 21:14 2阅读 0赞

[300. 最长递增子序列][300.]

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
    
    子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
    
    示例 1：
    
    输入：nums = [10,9,2,5,3,7,101,18]
    输出：4
    解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
    示例 2：
    
    输入：nums = [0,1,0,3,2,3]
    输出：4
    示例 3：
    
    输入：nums = [7,7,7,7,7,7,7]
    输出：1
     
    提示：
    
    1 <= nums.length <= 2500
    -104 <= nums[i] <= 104

![1fc5645df5f8cc674b420e69ca26afde.png][]

题解：

`dp[i]` 表示当前元素的递增子集个数

*  元素 1: 因为没有比它小的元素，所以递增子集数为 1
 *  元素 7：递增子集有：`1、 17` 即 `1 + dp[0]`
 *  元素 2：递增子集有：因为 `7` 比 `2` 大，所以只有 `1、 12`，即 `1 + dp[0]`
 *  元素 5：递增子集有：`1 、 15、 125`，即 `1 + dp[2]`
 *  如此类推就能推出 `dp[i]`

class Solution:
        def lengthOfLIS(self, nums: List[int]) -> int:
            n = len(nums)
            if n == 1:
                return 1
    
            dp = [1] * n
    
            res = 1
            for i in range(n):
                for j in range(i):
                    # 当前元素与它之前所有的元素进行比较，若之前元素比当前元素大，则跳过不考虑，只需要考虑比它小的即可
                    if nums[i] > nums[j]:
                        dp[i] = max(dp[j] + 1, dp[i])
    
                res = max(res, dp[i])
    
            return res

> 参考：[【算法太难了】【23】最长递增子序列-动态规划][23_-]

[300.]: https://leetcode.cn/problems/longest-increasing-subsequence/
[1fc5645df5f8cc674b420e69ca26afde.png]: https://img-blog.csdnimg.cn/img_convert/1fc5645df5f8cc674b420e69ca26afde.png
[23_-]: https://www.bilibili.com/video/BV19b4y1R7K3?spm_id_from=333.337.search-card.all.click&vd_source=a1a15e6ff8ef82a89528677058c6eeda