动态规划进阶：Python实现最长递增子序列（LIS）问题及其优化_python lis
介绍
最长递增子序列（Longest Increasing Subsequence，简称 LIS）是一个经典的动态规划问题，广泛应用于算法设计和问题求解中。它的基本目标是从一个给定的数列中找到一个递增的子序列，使得子序列的长度尽可能长。LIS问题有很多应用场景，包括图形学、股票交易预测等问题中。
本文将带领你从动态规划的基本方法入手，逐步深入学习如何解决 LIS 问题，并且介绍几种优化方法，让解决方案在大数据情况下更高效。
问题描述
给定一个整数数组，求其中最长递增子序列的长度。子序列是从原数组中删除一些元素（不改变其相对顺序）得到的数组。
示例
输入: nums = [10, 9, 2, 5, 3, 7, 101, 18]
输出: 4
解释: 最长递增子序列是 [2, 3, 7, 101]，其长度为 4。
1. 动态规划的基本解法
动态规划思想
我们可以通过动态规划的思想来求解 LIS 问题。具体步骤如下：
-
定义状态：
定义一个数组dp，其中dp[i]表示以第i个元素为结尾的最长递增子序列的长度。 -
状态转移：
对于每一个元素nums[i]，我们遍历其之前的元素nums[j]（j < i），如果nums[j] < nums[i]，那么可以将nums[i]加入到以nums[j]为结尾的递增子序列中，此时dp[i]的值为dp[j] + 1。 -
初始化：
每个位置的初始值为1，因为每个元素至少可以构成一个长度为 1 的子序列（即该元素本身）。 -
结果：
最后，返回dp数组中的最大值，表示最长递增子序列的长度。
代码实现
def lengthOfLIS(nums): if not nums: return 0 # 初始化dp数组，长度与nums相同，每个位置的值为1 dp = [1] * len(nums) # 遍历每个元素 for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) # 返回dp数组中的最大值 return max(dp)复杂度分析
- 时间复杂度：
O(n^2)，其中n是数组的长度。每个元素都需要遍历一次数组中的前面元素。 - 空间复杂度：
O(n)，需要一个dp数组来存储每个位置的子序列长度。
2. 使用二分查找进行优化
虽然上述的动态规划方法已经能正确求解问题，但对于较大的输入数据，时间复杂度为 O(n^2)，会导致效率较低。我们可以通过结合二分查找优化该算法。
优化思想
我们通过使用二分查找来降低时间复杂度。在二分查找中，我们尝试在每次计算时，不仅要找到最长递增子序列的长度，还要维护一个辅助数组 sub，其作用是：
sub数组中的元素保持递增顺序。sub[i]表示长度为i+1的递增子序列的最后一个元素。
具体步骤如下：
- 对每个元素
nums[i]，通过二分查找找到sub数组中第一个大于或等于nums[i]的位置。 - 如果找到了该位置，则将其更新为
nums[i]。 - 如果没有找到，则将
nums[i]加入到sub数组的末尾。
优化后的 Python 实现
import bisectdef lengthOfLIS(nums): sub = [] for num in nums: # 找到第一个大于等于num的位置 idx = bisect.bisect_left(sub, num) if idx == len(sub): # 如果没有找到，说明num比所有的元素都大，加入到sub的末尾 sub.append(num) else: # 如果找到了，更新该位置的元素 sub[idx] = num return len(sub)时间复杂度
- O(n log n)：遍历数组 + 二分查找。
代码实现
def length_of_lis_optimized(nums): tails = [] for num in nums: # 二分查找插入位置 left, right = 0, len(tails) while left < right: mid = (left + right) // 2 if tails[mid] < num: left = mid + 1 else: right = mid # 替换或追加 if left == len(tails): tails.append(num) else: tails[left] = num return len(tails)3. 代码测试与验证
测试用例
test_cases = [ ([10, 9, 2, 5, 3, 7, 101, 18], 4), ([0, 1, 0, 3, 2, 3], 4), ([7, 7, 7, 7], 1), ([], 0)]for nums, expected in test_cases: assert length_of_lis_optimized(nums) == expected性能对比
4. 总结与对比
传统动态规划方法
- 时间复杂度：
O(n^2)，适用于较小的输入数据。 - 空间复杂度：
O(n)，只需要一个dp数组。
优化后的二分查找方法
- 时间复杂度：
O(n log n)，适用于较大的输入数据，效率更高。 - 空间复杂度：
O(n)，需要一个辅助数组sub。
在实际应用中，如果问题规模较大，推荐使用优化后的二分查找方法，它能显著提高算法效率。
5. 实际应用
LIS 问题不仅仅是一个学术性问题，它在许多实际场景中都有应用。例如：
- 股票买卖问题：你可以将股价序列作为输入，计算最长递增子序列，表示你可以在这些天数中找到一组递增的价格，从而做出买入决策。
- 排序问题：LIS 可以用来找出给定序列中的最大递增子序列，帮助我们优化排序算法。
- 基因序列分析：在生物信息学中，LIS 用于比较不同的基因序列，寻找最相似的基因子序列。
6. 结语
本文详细讲解了如何使用动态规划求解最长递增子序列（LIS）问题，并通过二分查找优化了算法的时间复杂度。在处理更大规模的问题时，二分查找法的 O(n log n) 时间复杂度无疑更加高效。在实际应用中，LIS 问题不仅具有学术价值，还有很多实际应用场景，值得深入学习和掌握。
希望本文的讲解能够帮助你更好地理解 LIS 问题及其优化方法！
