这里先引用参考某博客中的概念：
LeetCode题目如下：https://leetcode-cn.com/problems/longest-common-subsequence/
class Solution: def longestCommonSubsequence(self, text1, text2): len_str1 = len(text1) len_str2 = len(text2) dp = [[0]*(len_str2+1) for _ in range(len_str1+1)] for i in range(1, len_str1+1): for j in range(1, len_str2+1): if text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[len_str1][len_str2]Reference：
https://blog.csdn.net/so_geili/article/details/53737001
LIS：
DP
# O(n^2) class Solution: # 将 dp 数组定义为：以 nums[i] 结尾的最长上升子序列的长度 # 那么题目要求的，就是这个 dp 数组中的最大者 # 以数组 [10, 9, 2, 5, 3, 7, 101, 18] 为例 # dp 的值： 1 1 1 2 2 3 4 4 def lengthOfLIS(self, nums): len_nums = len(nums) if len_nums <= 1: return len_nums dp = [1]*len_nums for i in range(1, len_nums): mid = [dp[j]+1 for j in range(i) if nums[i] > nums[j]] if mid: # 如果mid为非空列表 dp[i] = max(mid) # 最后要全部一看遍，取最大值 return max(dp)DP + 二分
# O(nlogn) class Solution: def lengthOfLIS(self, nums): size = len(nums) # 特判 if size < 2: return size # tail 数组的定义：长度为 i + 1 的上升子序列的末尾最小是几 # 遍历第 1 个数，直接放在有序数组 tail 的开头 tail = [nums[0]] for i in range(1, size): # 找到大于等于 num 的第 1 个数，试图让它变小 left = 0 # 因为有可能 num 比 tail 数组中的最后一个元素还要大， # 【逻辑 1】所以右边界应该设置为 tail 数组的长度 right = len(tail) while left < right: # 选左中位数不是偶然，而是有原因的，原因请见 LeetCode 第 35 题题解 mid = left + (right - left) // 2 # mid = (left + right) >> 1 if tail[mid] < nums[i]: # 中位数肯定不是要找的数，把它写在分支的前面 left = mid + 1 else: right = mid if left == len(tail): tail.append(nums[i]) else: # 因为【逻辑 1】，因此一定能找到第 1 个大于等于 nums[i] 的元素，因此无需再单独判断，直接更新即可 tail[left] = nums[i] return len(tail)
