最长递增子序列动态规划

最长递增子序列（Longest Increasing Subsequence，简称 LIS）是指在一个无序的序列中，找到一个尽可能长的子序列使得这个子序列中的所有元素都是递增的。动态规划是解决 LIS 问题的一种常用方法。

动态规划的思路是，先定义一个数组 dp，其中 dp[i] 表示以第 i 个元素为结尾的最长递增子序列的长度。那么，对于每一个 i，我们需要枚举在它之前的所有元素 j（j<i），如果当前的数 nums[i] 大于 nums[j]，那么 nums[i] 就可以接在 nums[j] 后面形成一个比 dp[j] 更长的递增子序列，此时 dp[i] 就可以更新为 dp[j]+1。最后，遍历一遍 dp 数组，找到其中的最大值，即为 LIS 的长度。

下面是 Python 代码实现：

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