最长重复子数组的变种：最多允许k次修改的最长重复子数组

我将为您讲解一个线性动态规划问题：在最多允许k次修改的情况下，找到两个数组的最长公共子数组长度。

问题描述
给定两个整数数组nums1和nums2，以及一个整数k。我们可以对任意数组中的元素进行最多k次修改（每次修改可以将一个元素的值改为任意整数）。请找出在最多进行k次修改的情况下，两个数组的最长公共子数组的长度。

示例
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7], k = 1
解释：将nums2中的4改为1，可以得到公共子数组[3,2,1]，长度为3。

解题思路

步骤1：理解问题本质
这个问题是经典最长公共子数组问题的变种，区别在于我们允许最多k次修改。这意味着在比较子数组时，我们允许最多k个位置不匹配。

步骤2：定义状态
我们定义dp[i][j][m]表示以nums1的第i个元素和nums2的第j个元素结尾，且使用了m次修改的公共子数组的最大长度。

步骤3：状态转移方程
考虑两种情况：

1. 如果nums1[i-1] == nums2[j-1]：

   • 不需要使用修改次数
   • dp[i][j][m] = dp[i-1][j-1][m] + 1

2. 如果nums1[i-1] != nums2[j-1]：

   • 如果m > 0（还有修改次数可用）：
     • 我们可以使用一次修改使这两个元素相等
     • dp[i][j][m] = dp[i-1][j-1][m-1] + 1
   • 否则：
     • dp[i][j][m] = 0（无法匹配）

步骤4：边界条件

• 当i=0或j=0时，dp[i][j][m] = 0
• 当m=0且nums1[i-1] != nums2[j-1]时，dp[i][j][0] = 0

步骤5：空间优化
由于dp[i][j][m]只依赖于dp[i-1][j-1][m]和dp[i-1][j-1][m-1]，我们可以使用滚动数组优化空间复杂度。

步骤6：算法实现

def findLength(nums1, nums2, k):
    m, n = len(nums1), len(nums2)
    # 使用二维dp数组，第三维用滚动方式处理
    dp_prev = [[0] * (k + 1) for _ in range(n + 1)]
    dp_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 m_used in range(k + 1):
                if nums1[i-1] == nums2[j-1]:
                    # 元素相等，不需要使用修改次数
                    dp_curr[j][m_used] = dp_prev[j-1][m_used] + 1
                else:
                    if m_used > 0:
                        # 使用一次修改次数
                        dp_curr[j][m_used] = dp_prev[j-1][m_used-1] + 1
                    else:
                        # 没有修改次数可用
                        dp_curr[j][m_used] = 0
                
                max_len = max(max_len, dp_curr[j][m_used])
        
        # 交换dp数组
        dp_prev, dp_curr = dp_curr, dp_prev
        # 重置当前dp数组
        for j in range(n + 1):
            for m_used in range(k + 1):
                dp_curr[j][m_used] = 0
    
    return max_len

步骤7：时间复杂度分析

• 时间复杂度：O(m × n × k)，其中m和n分别是数组长度
• 空间复杂度：O(n × k)

步骤8：示例验证
以示例nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7], k = 1为例：

• 最长公共子数组是[3,2,1]，长度为3
• 需要将nums2中的4修改为1（使用1次修改）

这个解法通过动态规划跟踪了在不同修改次数下的最长公共子数组长度，确保在允许的修改次数内找到最优解。