【算法题】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.结语
本人资历尚浅，发博客主要是记录与学习，欢迎大佬们批评指教！大家也可以在评论区多多交流，相互学习，共同成长。
