最长递增子序列（Longest Increasing Subsequence，简称 LIS）问题是动态规划中一个经典的算法问题。本文将介绍 LIS 问题及其动态规划解决方案。
问题定义
给定一个无序数组 nums，返回一个长度最小的子序列，该子序列的元素是按升序排列的，且子序列中任意相邻两个元素不相等。
动态规划解法
我们可以使用动态规划来解决 LIS 问题。以下是解题步骤：
- 初始化数组：创建一个长度与原数组相等的数组
dp，用于存储每个位置的最长递增子序列的长度。 - 遍历数组：从左到右遍历原数组，对于每个元素
nums[i]，遍历其左侧所有元素nums[j]（其中j < i）。 - 比较与更新：如果
nums[j] < nums[i]，则nums[i]可以接在nums[j]的子序列后面，此时dp[i]的值应该是dp[j] + 1。 - 记录最大值：在遍历过程中，记录下
dp数组中的最大值，即为 LIS 的长度。
示例
假设我们有数组 nums = [10, 9, 2, 5, 3, 7, 101, 18]。
经过计算，dp 数组为 [1, 1, 1, 2, 2, 3, 4, 4]。
因此，LIS 的长度为 4，可以取 [2, 3, 7, 101] 或 [2, 5, 7, 101]。