最长重复子数组的变种：最多允许k次替换的最长公共子数组（进阶版：替换代价为权重，限制替换操作总代价不超过C）
题目描述
给定两个整数数组 nums1 和 nums2，以及一个非负整数 k 和一个正整数 C。我们允许在匹配子数组时，最多进行 k 次“替换”操作，每次替换操作可以将 nums1 中某个位置的值改为任意整数（即与 nums2 中对应位置的值匹配），但每次替换操作有一个正整数代价（由给定的代价函数决定）。替换操作的总代价不能超过 C。我们需要找到最长的公共子数组长度，使得在满足替换次数不超过 k 且替换总代价不超过 C 的条件下，nums1 的一个子数组与 nums2 的一个子数组完全相同。
注意：
- 子数组必须是连续的。
- 替换操作只能用于
nums1中的元素（或对称地用于nums2，但题目通常约定修改一个数组）。 - 代价函数可以简化：假设代价为被替换元素的“改变量”的绝对值，即
abs(nums1[i] - newValue)，但newValue必须等于nums2[j]，因此单次替换代价为abs(nums1[i] - nums2[j])。 - 题目是经典“最多允许k次替换的最长重复子数组”的增强版，增加了代价限制，使得问题更接近实际匹配中的容错匹配。
解题步骤
这是一个二维动态规划问题，但状态需要额外记录替换次数和当前代价。为了降低复杂度，我们可以采用 滑动窗口 + 动态规划优化 或 三维DP。下面我将详细解释三维DP解法，因为其思路更直观，便于理解状态转移。
定义状态
设 dp[i][j][c] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组，在使用了恰好 c 次替换操作时的最小替换代价。但这样定义会导致状态数过大（因为代价维度是C）。更好的方法是将“代价”视为资源限制，用状态记录替换次数，并在转移时检查代价是否允许。
我们定义状态为：
dp[i][j][k_used] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组的长度，其中已经使用了 k_used 次替换操作，并且替换总代价不超过 C 的最大长度。但“长度”不适合直接做DP值，因为长度是我们要最大化的目标。我们可以转换思路：用 dp[i][j][k_used] 表示“以nums1[i-1]和nums2[j-1]结尾的公共子数组，在使用了k_used次替换时的最小总代价”，然后在所有代价 ≤ C 的状态中找最长的子数组长度。
但这样依然复杂。更实用的方法是：用二维DP + 第三维为替换次数，并在状态转移时累积代价，但代价累积后我们只关心是否 ≤ C。由于代价是累加的，我们可以在递推过程中计算代价，并只保留那些代价 ≤ C 的状态。
简化：假设代价是每次替换固定的（比如每次替换代价=1），那么只需记录替换次数即可，原题是“最多允许k次替换的最长公共子数组”，经典解法是滑动窗口或DP。但这里代价可变，我们需要调整。
重新规划状态
设 dp[i][j][k_used] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组，在使用恰好 k_used 次替换时的最小累计代价。如果无法形成这样的子数组，代价设为无穷大（INF）。
状态转移方程分两种情况：
-
如果
nums1[i-1] == nums2[j-1]，则不需要替换：
dp[i][j][k_used] = dp[i-1][j-1][k_used]（继承之前的代价）
但前提是i>1且j>1且dp[i-1][j-1][k_used] != INF，否则如果i==1或j==1，则这是一个新的子数组起点，代价为0。 -
如果
nums1[i-1] != nums2[j-1]，则可以选择替换（如果 k_used > 0）：
替换代价增加abs(nums1[i-1] - nums2[j-1])，所以：
dp[i][j][k_used] = dp[i-1][j-1][k_used-1] + cost
其中cost = abs(nums1[i-1] - nums2[j-1])。
同样，如果i==1或j==1，则之前代价为0。 -
初始条件：当 i=0 或 j=0 时，不存在以它结尾的子数组，我们可以不考虑这些状态，直接从 i=1,j=1 开始递推。但为了方便，我们可以将
dp[0][*][*]和dp[*][0][*]设为 INF，除了dp[0][0][0]=0这种虚拟状态。不过通常我们初始化每个 (i,j) 时，如果 nums1[i-1]==nums2[j-1]，则dp[i][j][0]=0，否则dp[i][j][1]=cost（如果k>=1）。
但这样定义 dp 值为代价，我们怎么得到最长长度？
我们需要另一个数组 len[i][j][k_used] 记录长度。但可以简化：因为 dp 值记录最小代价，只要 dp 值 ≤ C，就说明这个子数组可行，其长度就是当前连续匹配的长度，这个长度可以在递推时累积。
更好的方法：不记录代价在状态值里，而是将代价作为第四维，但那样状态太多。我们换个思路：
优化思路：二分答案 + 二维DP检查
我们可以二分查找最长长度 L，然后检查是否存在长度为 L 的公共子数组，使得替换次数 ≤ k 且替换总代价 ≤ C。
如何检查？
对于给定的长度 L，我们可以枚举所有起始位置 i 在 nums1，j 在 nums2，然后计算从 (i, j) 开始的长度为 L 的子数组的替换次数和总代价。但这样是 O(n1n2L) 的。
我们可以用前缀和优化：
先预处理 diff[i][j] = abs(nums1[i] - nums2[j])，然后对每个对齐位置偏移 p = i-j，在对应对齐的斜线上，用滑动窗口维护窗口内 diff 的和，找到窗口内 diff 的和 ≤ C 且窗口内非零 diff 的数量 ≤ k 的最大窗口长度。但这要枚举偏移 p，复杂度 O((n1+n2)*n1) 左右，稍复杂。
但更通用的检查方法是DP：
定义 f[i][j] 表示以 nums1[i] 和 nums2[j] 结尾的公共子数组，在替换代价 ≤ C 的前提下，最少替换次数。
但这里“替换次数最少”和“代价 ≤ C”是双重约束，我们可以反过来：在替换次数 ≤ k 下，最小化代价，看是否 ≤ C。
这可以通过二维DP，状态是 (i,j,used)，used 是替换次数，值为最小代价，然后看 used ≤ k 中是否有代价 ≤ C 的。
不过二分长度 L 后，我们只需判断是否存在长度 ≥ L 的子数组，这可以通过计算每个 (i,j) 结尾的最长匹配（满足代价约束）是否 ≥ L 来判断。
最终采用的DP解法（三维DP，记录长度）
我们设 dp[i][j][c] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组，在替换总代价恰好为 c 时的最大长度（c 从 0 到 C）。
初始化：dp 全为 0。
转移方程：
如果 nums1[i-1] == nums2[j-1]：
对于每个 c 从 0 到 C：
dp[i][j][c] = max(dp[i][j][c], dp[i-1][j-1][c] + 1)（如果 i>1 且 j>1），否则 dp[i][j][c]=1（当 i=1 或 j=1 时单独处理）。
如果 nums1[i-1] != nums2[j-1]，设 cost = abs(nums1[i-1] - nums2[j-1])：
对于每个 c 从 cost 到 C：
dp[i][j][c] = max(dp[i][j][c], dp[i-1][j-1][c-cost] + 1)（前提是 dp[i-1][j-1][c-cost] > 0 或 c==cost 且 i-1==0 或 j-1==0 时长度为1）。
注意：c 维度是代价，我们要让长度最大，所以 dp 值存储长度。
最后答案就是所有 i, j, c ≤ C 中 dp[i][j][c] 的最大值。
复杂度：O(n1 * n2 * C)，C 是代价上限，如果 C 很大，此法不可行。但在很多实际问题中 C 是较小的整数。
例子说明
设 nums1 = [1,3,5], nums2 = [3,1,5], k=1, C=2。
代价函数：cost = abs(nums1[i]-nums2[j])。
我们尝试 dp 过程：
初始化 dp 全 0。
i=1, j=1: nums1[0]=1, nums2[0]=3, 不等，cost=2，c=2 时 dp[1][1][2]=1。
i=1, j=2: 1 和 1 相等，c=0 时 dp[1][2][0]=1。
i=1, j=3: 1 和 5 不等，cost=4>2，忽略（代价超）。
i=2, j=1: 3 和 3 相等，c=0 时 dp[2][1][0]=max(0, dp[1][0][0]+1)，但 dp[1][0][0] 不存在，视为0，所以长度=1。
i=2, j=2: 3 和 1 不等，cost=2，c=2 时 dp[2][2][2]=max(0, dp[1][1][0]+1)，但 dp[1][1][0]=0，所以长度=1。
i=2, j=3: 3 和 5 不等，cost=2，c=2 时 dp[2][3][2]=max(0, dp[1][2][0]+1)，而 dp[1][2][0]=1，所以长度=2。
i=3, j=1: 5 和 3 不等，cost=2，c=2 时 dp[3][1][2]=max(0, dp[2][0][0]+1)=1。
i=3, j=2: 5 和 1 不等，cost=4>2，忽略。
i=3, j=3: 5 和 5 相等，c=0 时 dp[3][3][0]=dp[2][2][0]+1，但 dp[2][2][0]=0，所以长度=1。
最后检查所有 dp 值，最大长度是 dp[2][3][2]=2，即子数组 nums1[1..2]=[3,5] 与 nums2[2..3]=[1,5] 在替换 nums1[1] 从3改为1（代价2）后相同。
但这里替换次数是1（k=1满足），代价=2（C=2满足），所以答案是2。
总结步骤
- 确定代价计算方式（本题为绝对值差）。
- 定义三维数组 dp[i][j][c] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组，在总替换代价为 c 时的最大长度。
- 初始化 dp 为0。
- 遍历 i 从 1 到 n1，j 从 1 到 n2：
- 如果两数相等，则对每个 c 从 0 到 C：若 dp[i-1][j-1][c] 有值，则 dp[i][j][c] = dp[i-1][j-1][c]+1；否则若 i=1 或 j=1，则 dp[i][j][c]=1。
- 如果两数不等，计算 cost，对每个 c 从 cost 到 C：若 dp[i-1][j-1][c-cost] 有值，则 dp[i][j][c] = max(dp[i][j][c], dp[i-1][j-1][c-cost]+1)；否则若 i=1 或 j=1 且 c==cost，则 dp[i][j][c]=1。
- 最终答案为所有 dp[i][j][c] 的最大值，且满足替换次数 ≤ k 吗？等等，我们还没记录替换次数！
问题：我们只记录了总代价，没记录替换次数。所以需增加一维记录替换次数，变为四维 dp[i][j][c][r]：代价 c，替换次数 r 时的最大长度，但这样状态太大。
调整：既然替换次数 ≤ k 且代价 ≤ C，我们可以将代价视为“资源”，记录最少替换次数达到某个代价的状态，但更直接的方法是：
用 dp[i][j][r] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组，在替换次数为 r 时的最小总代价。
然后如果 dp[i][j][r] ≤ C，则其对应的长度可以由另一个数组 len[i][j][r] 记录。
转移：
若 nums1[i-1]==nums2[j-1]，则 dp[i][j][r] = dp[i-1][j-1][r]，len=len[i-1][j-1][r]+1。
若不相等，则 dp[i][j][r] = dp[i-1][j-1][r-1] + cost，len=len[i-1][j-1][r-1]+1（若 r>0）。
初始化：dp[0][][]=INF，dp[][0][]=INF，dp[0][0][0]=0，len[0][0][0]=0。
最后，找出所有 r ≤ k 且 dp[i][j][r] ≤ C 的 len[i][j][r] 的最大值。
复杂度 O(n1n2k)，可行。
最终算法
- 初始化 dp[n1+1][n2+1][k+1] 为无穷大，len[n1+1][n2+1][k+1]=0。
- dp[0][0][0]=0, len[0][0][0]=0。
- 遍历 i 从 0 到 n1，j 从 0 到 n2（i,j 不同时为0）：
如果 i==0 或 j==0，则 dp[i][j][0]=0, len[i][j][0]=0（空子数组）。
否则，对于 r 从 0 到 k：- 相等情况：若 i>0 且 j>0 且 dp[i-1][j-1][r] ≠ INF，则 dp[i][j][r] = dp[i-1][j-1][r]，len[i][j][r] = len[i-1][j-1][r]+1。
- 不相等且 r>0：cost = abs(nums1[i-1]-nums2[j-1])，若 dp[i-1][j-1][r-1]+cost ≤ C 且 dp[i-1][j-1][r-1]≠INF，则更新 dp[i][j][r]=dp[i-1][j-1][r-1]+cost，len[i][j][r]=len[i-1][j-1][r-1]+1。
注意：如果同时满足相等和不相等，取 len 更大的。
- 最终答案 = max{len[i][j][r]} 对所有 i,j,r 满足 r ≤ k 且 dp[i][j][r] ≤ C。
此算法时间复杂度 O(n1n2k)，空间可通过滚动数组优化为 O(n2*k)。