最长重复子数组的变种：最多允许k次修改的最长公共子数组（进阶版：修改代价与次数限制）

问题描述

给定两个整数数组 nums1 和 nums2，以及一个整数 k 和一个修改代价数组 cost（可选，若不存在则认为每次修改代价为1）。我们定义一次“修改”操作为：可以将某个数组在某个位置的值改变为任意整数，但需要付出相应的代价（代价取决于原值和新值，若未提供代价数组，则统一为1）。

目标：找到最长的公共子数组（连续），使得在最多进行 k 次修改（或总修改代价不超过 k）的前提下，两个子数组完全匹配（即修改后相等）。输出这个最长公共子数组的长度。

示例：

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

修改代价：每次修改代价为1。

• 最长公共子数组可以是 [2,3,4,5]，但需要修改 nums1 中的 1→? 或 nums2 中的 1→? 等，实际上需要检查。
  解释：最长公共子数组是 [4,5]，长度2，无需修改。但若允许1次修改，可得到 [2,3,4,5]，长度4（例如将 nums2 中的1改为2，则从索引0开始的子数组 [2,3,1,4] 修改一次可得 [2,3,2,4] 仍不匹配，需仔细设计）。

实际更清晰的例子：

nums1 = [1, 3, 5, 7, 9]
nums2 = [2, 3, 5, 8, 9]
k = 1

若修改代价为1，则最长公共子数组为 [3,5,7] 与 [3,5,8] 修改7→8 或 8→7 一次，得到 [3,5,7] 或 [3,5,8]，长度3。注意公共子数组需连续且位置对应。

问题分析

此问题是最长公共子数组（最长重复子数组）的变种，允许最多k次修改（或总代价≤k）以使子数组匹配。核心在于：对于每一对起始位置 (i,j)，我们需要找到最长的长度 L，使得子数组 nums1[i:i+L] 和 nums2[j:j+L] 中，不同的元素个数（或总修改代价）不超过 k。

解题思路

我们可以用动态规划，但需记录不同位置匹配时，已使用的修改次数（或代价）。

状态定义

设 dp[i][j][t] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的子数组，在最多使用 t 次修改（或代价不超过 t） 的情况下，能得到的公共子数组的最大长度。

但这样三维数组可能过大（若 n,m 为数组长度，k 可能很大）。我们可优化为二维滑动窗口或二分+哈希，但这里介绍二维DP+第三维为使用修改次数的方法（适用于 k 较小的情况）。

转移方程

考虑 nums1[i-1] 和 nums2[j-1]：

• 若 nums1[i-1] == nums2[j-1]，则不需要修改，dp[i][j][t] = dp[i-1][j-1][t] + 1。
• 若 nums1[i-1] != nums2[j-1]，则我们可以选择修改其中一个以使其相等，消耗一次修改（或代价 c）。若 t > 0，则 dp[i][j][t] = dp[i-1][j-1][t-1] + 1（这里假设修改代价为1，若代价数组存在，则需根据代价减少对应的 t'，而非固定减1）。
• 注意：如果 t=0 且两字符不等，则不能扩展，dp[i][j][0] = 0。

最终答案为所有 dp[i][j][t] 的最大值，其中 t ≤ k。

复杂度

时间复杂度 O(nmk)，空间复杂度 O(nmk) 或优化为 O(m*k) 滚动数组。

详细步骤

我们以例子 nums1 = [1,3,5,7,9], nums2 = [2,3,5,8,9], k=1 说明。

1. 初始化：

   • 数组索引从1开始方便表示，dp[i][j][t] 表示以 i,j 结尾的子数组在最多 t 次修改下的最大长度。
   • 创建三维数组，大小为 (n+1)×(m+1)×(k+1)，初始化为0。

2. 遍历 i 从 1 到 n，j 从 1 到 m，t 从 0 到 k：

   • 如果 nums1[i-1] == nums2[j-1]：
     • 对于每个 t，dp[i][j][t] = dp[i-1][j-1][t] + 1。
   • 否则：
     • 如果 t >= 1（即还可修改）：
       • dp[i][j][t] = dp[i-1][j-1][t-1] + 1（修改一次使它们相等）。
     • 如果 t == 0：
       • dp[i][j][0] = 0（无法修改，不能形成公共子数组）。

3. 在遍历过程中记录最大值。

手动模拟（k=1）：

• i=1,j=1: nums1[0]=1, nums2[0]=2 不等，t=0 则 dp=0；t=1 则 dp[1][1][1] = dp[0][0][0] + 1 = 0+1=1。
• i=1,j=2: 1 vs 3 不等，t=0:0, t=1:1。
• ... 直到 i=2,j=2: 3==3 相等，t=0: dp[2][2][0] = dp[1][1][0]+1 = 0+1=1；t=1: dp[2][2][1] = dp[1][1][1]+1 = 1+1=2。
• 继续计算，最后得到的最大值是3，对应子数组 [3,5,7] 与 [3,5,8] 修改一次。

优化

当 k 较小时，上述 DP 可行。若 k 较大，可转化为最长子数组使得不同元素个数 ≤ k 的问题，用滑动窗口（双指针）对每对偏移量进行，复杂度 O((n+m)*min(n,m))。具体为：枚举对齐偏移 d = i-j，然后对每个偏移用双指针维护窗口内不同元素个数 ≤ k 的最大窗口长度。

扩展：带修改代价

若每次修改代价不同（如代价为 |a-b| 或由代价矩阵给出），则第三维应为代价上限，DP 需按代价转移，类似背包思路。

代码框架（DP版本，k较小）

def longestCommonSubarrayWithModification(nums1, nums2, k):
    n, m = len(nums1), len(nums2)
    dp = [[[0]*(k+1) for _ in range(m+1)] for _ in range(n+1)]
    max_len = 0
    for i in range(1, n+1):
        for j in range(1, m+1):
            for t in range(k+1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j][t] = dp[i-1][j-1][t] + 1
                else:
                    if t > 0:
                        dp[i][j][t] = dp[i-1][j-1][t-1] + 1
                    else:
                        dp[i][j][t] = 0
                max_len = max(max_len, dp[i][j][t])
    return max_len

总结

这个问题是最长公共子数组的灵活扩展，通过引入修改次数限制，增加了问题的实用性（如允许容错的匹配）。核心是在状态中记录已使用的修改资源，在匹配或修改时进行转移。当 k 较大时，可切换为基于滑动窗口的高效方法。