序列问题
序列问题是动态规划中的经典问题，包括最长递增子序列、最长公共子序列等。
最长递增子序列
问题描述
给定一个序列，找出其中最长的递增子序列的长度。
实现
python
def longest_increasing_subsequence(nums):
if not nums:
return 0
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)
return max(dp)
# 示例
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print("最长递增子序列长度:", longest_increasing_subsequence(nums)) # 4优化版本（二分查找）
python
def lis_binary_search(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)
# 示例
print("最长递增子序列长度(优化):", lis_binary_search(nums)) # 4最长连续序列
问题描述
给定一个未排序的整数数组，找出最长连续序列的长度。
实现
python
def longest_consecutive(nums):
num_set = set(nums)
longest = 0
for num in num_set:
if num - 1 not in num_set:
current_num = num
current_length = 1
while current_num + 1 in num_set:
current_num += 1
current_length += 1
longest = max(longest, current_length)
return longest
# 示例
nums = [100, 4, 200, 1, 3, 2]
print("最长连续序列长度:", longest_consecutive(nums)) # 4最长回文子串
问题描述
给定一个字符串，找出最长的回文子串。
实现
python
def longest_palindromic_substring(s):
if not s:
return ""
n = len(s)
dp = [[False] * n for _ in range(n)]
start = 0
max_length = 1
# 单个字符都是回文
for i in range(n):
dp[i][i] = True
# 检查两个字符
for i in range(n - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
start = i
max_length = 2
# 检查长度大于2的子串
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
start = i
max_length = length
return s[start:start + max_length]
# 示例
s = "babad"
print("最长回文子串:", longest_palindromic_substring(s)) # "bab" 或 "aba"编辑距离
问题描述
计算两个字符串之间的编辑距离（将一个字符串转换为另一个字符串所需的最少操作次数）。
实现
python
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始化
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# 填充DP表
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(
dp[i - 1][j] + 1, # 删除
dp[i][j - 1] + 1, # 插入
dp[i - 1][j - 1] + 1 # 替换
)
return dp[m][n]
# 示例
print("编辑距离:", edit_distance("horse", "ros")) # 3复杂度分析
| 问题 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| LIS (DP) | O(n²) | O(n) |
| LIS (二分) | O(n log n) | O(n) |
| 最长连续序列 | O(n) | O(n) |
| 最长回文子串 | O(n²) | O(n²) |
| 编辑距离 | O(mn) | O(mn) |