【LeetCode】300. Longest ascending subsequence

1. subject

2. thought

dp topic

• state ： set up dp[i] Said to nums[i] by The maximum length of ascending subsequence obtained at the end
• Strategy ： How to get the state transition formula ？
  dp[i] Meeting rely on i All the numbers before j, among $j<i$, Recursion is
  $$dp[i]=dp[j]+1,ifnum[i]>num[j]$$
  Keep updating to get the maximum

3. Code

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums) #  Itself is 1 
        # s  It represents the interval length  
        for i in range(0,len(nums)):
            for j in range(0,i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[j]+1,dp[i])
        res = dp[0]
        for i in range(len(nums)):
            res = max(res,dp[i])
        return res