线性动态规划：最长重复子数组的变种——最多允许删除k个元素的最长公共子数组

让我为您讲解这个线性动态规划问题。

问题描述

给定两个整数数组nums1和nums2，以及一个整数k。我们需要找到两个数组中最长的公共子数组，但是允许从公共子数组中最多删除k个元素。也就是说，我们寻找的公共子数组在删除最多k个元素后，剩下的部分在两个数组中都是连续出现的。

解题思路

这个问题是经典的最长重复子数组问题的变种。我们可以使用动态规划来解决，但需要记录在匹配过程中已经删除的元素数量。

详细解题步骤

步骤1：定义状态

设dp[i][j][d]表示以nums1的第i个元素和nums2的第j个元素结尾，且已经删除了d个元素的最长公共子数组长度。

步骤2：状态转移方程

对于每个位置(i, j)和删除次数d，我们考虑两种情况：

1. 当前元素匹配
   如果nums1[i-1] == nums2[j-1]，那么我们可以直接扩展子数组：
   dp[i][j][d] = dp[i-1][j-1][d] + 1

2. 当前元素不匹配，但还有删除次数
   如果nums1[i-1] != nums2[j-1] 且 d < k：

   • 删除nums1中的当前元素：dp[i][j][d+1] = dp[i-1][j][d]
   • 删除nums2中的当前元素：dp[i][j][d+1] = dp[i][j-1][d]

步骤3：初始化

• 当i=0或j=0时，dp[i][j][d] = 0（没有元素可以匹配）
• 初始时，所有删除次数为0的情况：dp[i][j][0] = 0

步骤4：算法实现

def longestCommonSubarrayWithDeletions(nums1, nums2, k):
    m, n = len(nums1), len(nums2)
    # 创建三维DP数组
    dp = [[[0] * (k + 1) for _ in range(n + 1)] for _ in range(m + 1)]
    max_len = 0
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            for d in range(k + 1):
                # 情况1：当前元素匹配
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j][d] = dp[i-1][j-1][d] + 1
                    max_len = max(max_len, dp[i][j][d])
                
                # 情况2：当前元素不匹配但还有删除次数
                if d < k:
                    # 删除nums1中的当前元素
                    dp[i][j][d+1] = max(dp[i][j][d+1], dp[i-1][j][d])
                    # 删除nums2中的当前元素  
                    dp[i][j][d+1] = max(dp[i][j][d+1], dp[i][j-1][d])
                    max_len = max(max_len, dp[i][j][d+1])
    
    return max_len

步骤5：空间优化

由于三维DP数组空间复杂度较高，我们可以使用滚动数组优化：

def longestCommonSubarrayWithDeletions_optimized(nums1, nums2, k):
    m, n = len(nums1), len(nums2)
    # 使用二维DP数组，只保存前一行的状态
    prev = [[0] * (k + 1) for _ in range(n + 1)]
    curr = [[0] * (k + 1) for _ in range(n + 1)]
    max_len = 0
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            for d in range(k + 1):
                curr[j][d] = 0
                # 当前元素匹配
                if nums1[i-1] == nums2[j-1]:
                    curr[j][d] = prev[j-1][d] + 1
                    max_len = max(max_len, curr[j][d])
                
                # 当前元素不匹配但还有删除次数
                if d < k:
                    # 删除nums1中的当前元素
                    curr[j][d+1] = max(curr[j][d+1], prev[j][d])
                    # 删除nums2中的当前元素
                    curr[j][d+1] = max(curr[j][d+1], curr[j-1][d])
                    max_len = max(max_len, curr[j][d+1])
        
        prev, curr = curr, prev
    
    return max_len

示例分析

假设nums1 = [1,2,3,4,5], nums2 = [1,3,2,4,5], k = 1

• 最长公共子数组是[1,3,4,5]（删除nums1中的2或nums2中的2）
• 长度为4

复杂度分析

• 时间复杂度：O(m × n × k)，其中m和n分别是两个数组的长度
• 空间复杂度：O(n × k)（优化后）

这个算法通过动态规划巧妙地处理了允许删除元素的情况，是经典最长重复子数组问题的有用扩展。