为什么在恢复最长递增序列时需要祖先数组？

在解决最长递增子序列（Longest Increasing Subsequence, LIS）问题时，祖先数组（也称为前驱数组或路径数组）是一个非常有用的辅助数据结构。它主要用于记录每个元素在LIS中的前一个元素的索引，从而在找到LIS后能够方便地恢复出整个序列。

基础概念

最长递增子序列问题是在一个给定的序列中找到一个最长的子序列，使得这个子序列中的元素是严格递增的。例如，在序列 [10, 9, 2, 5, 3, 7, 101, 18] 中，最长递增子序列是 [2, 3, 7, 101]。

为什么需要祖先数组

在动态规划求解LIS的过程中，我们通常会维护一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。然而，仅凭 dp 数组，我们无法直接恢复出LIS的具体序列。

祖先数组的作用就是记录每个元素的前驱元素，这样在找到LIS的长度后，可以通过回溯祖先数组来恢复出整个LIS。具体来说，如果我们知道 dp[i] 的值，并且知道 i 的前驱是 j（即 ancestors[i] = j），那么我们就可以从 i 回溯到 j，再从 j 回溯到 j 的前驱，依此类推，直到回溯到序列的起点，从而得到整个LIS。

相关优势

• 恢复序列：祖先数组使得在找到LIS长度后能够方便地恢复出整个LIS。
• 路径清晰：通过祖先数组，可以清晰地看到每个元素在LIS中的位置和前驱关系。

类型与应用场景

• 类型：祖先数组是一种辅助数据结构，用于记录动态规划过程中的状态转移路径。
• 应用场景：除了最长递增子序列问题外，祖先数组还可以应用于其他需要回溯路径的动态规划问题，如编辑距离、最短路径等。

示例代码

以下是一个使用动态规划和祖先数组求解LIS问题的示例代码（Python）：

def lengthOfLIS(nums):
    if not nums:
        return 0

    dp = [1] * len(nums)
    ancestors = [-1] * len(nums)
    max_length = 1
    max_index = 0

    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                ancestors[i] = j
                if dp[i] > max_length:
                    max_length = dp[i]
                    max_index = i

    # 恢复LIS
    lis = []
    while max_index != -1:
        lis.append(nums[max_index])
        max_index = ancestors[max_index]
    lis.reverse()

    return max_length, lis

# 示例
nums = [10, 9, 2, 5, 3, 7, 101, 18]
length, lis = lengthOfLIS(nums)
print("Length of LIS:", length)
print("LIS:", lis)

参考链接

• 最长递增子序列（LIS）问题详解

通过上述方法和示例代码，可以清晰地理解为什么在恢复最长递增序列时需要祖先数组，以及如何使用它来解决问题。