300. 最长递增子序列

链接

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]
"""