链接
https://leetcode.cn/problems/longest-increasing-subsequence/description/
思路
经典DP题目。
我们用dp[i]代表了第i个元素为最终子序列长度的最长递增子序列的长度。
总体思想就是，对于某个子序列i，去遍历它前面的dp[0~i-1]，看看满足条件的dp[0~i-1]中最长的是哪个。
所以状态转移方程为： dp[i] = max(dp[i], dp[j]+1)。
所以时间复杂度为O(n**2)
代码
class Solution: def lengthOfLIS(self, nums) -> int: dp = [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[j] + 1, dp[i]) return max(dp) """ [0,1,0,3,2,3] """