【算法题】300. 最长递增子序列-力扣(LeetCode)

【算法题】300. 最长递增子序列-力扣(LeetCode)

1.题目

下方是力扣官方题目的地址

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

进阶：

• 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

2.题解

思路

这题是一道典型的动态规划的题目，和我之前的一道题有点相似，大家可以看看我的这一篇文章：

【算法题】322.零钱兑换-力扣(LeetCode)

为什么这题可以用动态规划，因为它要求求最长递增子序列，而最长递增子序列是如何得出来的呢？

很显然，我们可以将这个问题转换为一个子问题，找出问题之间的状态转移方程，再利用动态规划，这题就可以解决了。

我们可以初始化一个dp数组，我们以nums = [10,9,2,5,3,7,101,18]为例，dp[3]的意思就是：

子序列[10,9,2,5]中的最长递增子序列的长度,很显然是[2,5]，所以dp[3]=2。

然后我们可以画出这样一张图（Subsequence代表最长递增子序列）

那么什么可以影响到dp[i]的值呢？

前面的dp[i-1],dp[i-2]…都可以影响到它，因为dp[i]的得来是：

继承dp[i-1]或者dp[i-2]…的递增子序列，然后在此的基础上，长度+1

而继承是需要有条件的：

因为需要满足递增，所以我们需要num[i]大于被继承的序列的最大值，而由于是递增序列，则往往被继承的序列的最后一个数就是最大值，也就是说，继承必须满足：num[i]>num[j] (j代表被继承的子序列的最后一个数的位置)

所以就可以得出状态转移方程：

dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]

得到了状态转移方程，这道题基本上也是解决了。

Python代码

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n=len(nums)
        dp=[1]*n            
        for i in range(n):
            for j in range(i):
                if nums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1)
        return max(dp)

3.结语

本人资历尚浅，发博客主要是记录与学习，欢迎大佬们批评指教！大家也可以在评论区多多交流，相互学习，共同成长。