动态规划最长上升子序列

动态规划最长上升子序列问题是指给定一个长度为n的数列，求它的最长上升子序列长度。其中，最长上升子序列是指在原数列中，找到一个严格递增的子序列，且该子序列元素个数最多。

动态规划最长上升子序列算法如下：

1. 定义状态：设dp[i]表示以i结尾的最长上升子序列长度。

2. 初始化状态：dp[i]=1，因为任何一个数都可以看做长度为1的上升子序列。

3. 状态转移方程：对于每个i，我们需要枚举其前面所有比它小的数j，然后更新dp[i]的值。即如果nums[j]<nums[i]，那么dp[i]=max(dp[i],dp[j]+1)。

4. 最终结果：最长上升子序列的长度为max(dp[i])，其中0<=i<n。

下面是Python代码实现：

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

时间复杂度为O(n^2)，空间复杂度为O(n)。如果需要更快的算法，可以使用二分查找将时间复杂度优化到O(nlogn)。