跳到主要内容

序列问题

在动态规划中，序列问题是一类常见的问题，通常涉及对序列（如数组、字符串等）进行操作或分析。这类问题的核心在于如何通过子问题的解来构建原问题的解。序列问题通常包括最长递增子序列、最长公共子序列、编辑距离等。

什么是序列问题？​

序列问题是指在一组有序的元素（如数组或字符串）中，寻找满足特定条件的子序列或子数组。这类问题通常可以通过动态规划来解决，因为动态规划能够有效地将问题分解为子问题，并通过存储子问题的解来避免重复计算。

动态规划的核心思想​

动态规划的核心思想是分治和记忆化。通过将问题分解为更小的子问题，并存储子问题的解，我们可以避免重复计算，从而提高算法的效率。

最长递增子序列（LIS）​

最长递增子序列（Longest Increasing Subsequence, LIS）是序列问题中的一个经典问题。给定一个整数序列，找到其中最长的严格递增子序列的长度。

问题描述​

给定一个整数数组 nums，找到其中最长的严格递增子序列的长度。

示例：

python
输入: nums = [10, 9, 2, 5, 3, 7, 101, 18]
输出: 4
解释: 最长的递增子序列是 [2, 3, 7, 101]，长度为 4。

动态规划解法​

我们可以使用动态规划来解决这个问题。定义一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。对于每个 i，我们需要遍历 0 到 i-1 的所有元素，如果 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)。

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

复杂度分析​

  • 时间复杂度：O(n²)，其中 n 是数组的长度。
  • 空间复杂度：O(n)，用于存储 dp 数组。

最长公共子序列（LCS）​

最长公共子序列（Longest Common Subsequence, LCS）是另一个经典的序列问题。给定两个字符串，找到它们的最长公共子序列。

问题描述​

给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。

示例：

python
输入: text1 = "abcde", text2 = "ace"
输出: 3
解释: 最长公共子序列是 "ace"，长度为 3。

动态规划解法​

我们可以使用动态规划来解决这个问题。定义一个二维数组 dp，其中 dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

python
def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 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[m][n]

复杂度分析​

  • 时间复杂度：O(m * n)，其中 m 和 n 分别是两个字符串的长度。
  • 空间复杂度：O(m * n)，用于存储 dp 数组。

实际应用场景​

序列问题在实际中有广泛的应用，例如：

  • 生物信息学：在 DNA 序列比对中，LCS 用于找到两个 DNA 序列的相似部分。
  • 文本处理：在自然语言处理中，LCS 可以用于比较两个文本的相似性。
  • 金融分析：在股票价格序列中，LIS 可以用于分析股票价格的上升趋势。

总结​

序列问题是动态规划中的一类重要问题，通过将问题分解为子问题并存储子问题的解，我们可以有效地解决这些问题。本文介绍了最长递增子序列和最长公共子序列两个经典问题，并提供了相应的动态规划解法。

附加资源与练习​

  • 练习 1：实现一个算法，找到给定数组中的最长递减子序列。
  • 练习 2：尝试解决编辑距离问题，给定两个单词 word1 和 word2，找到将 word1 转换为 word2 所需的最少操作数。
提示

如果你对动态规划的其他问题感兴趣，可以继续学习背包问题、矩阵链乘法等问题。