[dynamic programming] longest increasing subsequence

Give you an array of integers nums , Find the length of the longest strictly increasing subsequence .

Input ：nums = [10,9,2,5,3,7,101,18]
Output ：4
explain ： The longest increasing subsequence is [2,3,7,101], So the length is 4 .

Reference link https://leetcode-cn.com/problems/longest-increasing-subsequence/

Definition ：$dp[i]$ Show from 0 To $i$ The longest increasing subsequence by far

The boundary conditions ：$dp[i]=1,i$​​​ from ​$0$ To $N-1$

State transition equation ：$dp[i]=max(dp[j])+1,ifnums[i]>nums[j]$​

explain ：​ Every index number bit $i$​​ The longest increasing subsequence up to , Equal to traversing from 0 To i So far the dp Maximum value , At the same time, the value corresponding to the maximum value should be compared with the index number i The value should be small

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        N = len(nums)
        dp = [1]*N
        ans = 1
        for i in range(1,N):
            for j in range(i):
                if nums[j]<nums[i]:
                    dp[i] = max(dp[i],dp[j]+1)
                    ans = max(ans,dp[i])
        return ans

Find the largest dp When , Binary search can be used to optimize , bring O(nlogn)