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

线性动态规划：最长重复子数组的变种——最多允许删除k个元素的最长公共子数组 题目描述 给定两个整数数组 nums1 和 nums2 ，以及一个非负整数 k ，要求找到最长的公共子数组的长度，且允许从 nums1 或 nums2 中 最多删除 k 个元素 （删除操作仅针对当前数组的任意位置，但子数组在原数组中的相对顺序必须保留）。 例如： 输出： 3 解释：公共子数组 [2, 3, 4] 或 [2, 3, 5] 在删除 nums2 中的 1 后得到。 解题思路 核心挑战 子数组要求连续 ：普通最长公共子数组（LCS）要求完全连续匹配，但本题允许最多删除 k 个元素，相当于允许部分不匹配。 删除操作灵活性 ：删除可发生在任意数组的任意位置，需动态规划状态记录当前已删除数量。 状态定义 设 dp[i][j][d] 表示以 nums1 的第 i 位和 nums2 的第 j 位为结尾的公共子数组的长度，且当前已累计删除 d 个元素（ d ≤ k ）。 状态转移 若 nums1[i-1] == nums2[j-1] ： 直接扩展前一个状态： dp[i][j][d] = dp[i-1][j-1][d] + 1 。 若 nums1[i-1] != nums2[j-1] ： 选择删除 nums1 的当前元素： dp[i][j][d] = dp[i-1][j][d-1] + 1 （需 d ≥ 1 ）。 选择删除 nums2 的当前元素： dp[i][j][d] = dp[i][j-1][d-1] + 1 （需 d ≥ 1 ）。 选择不匹配（重置子数组）： dp[i][j][d] = 0 。 取三者最大值。 初始化 dp[0][j][d] = 0 ， dp[i][0][d] = 0 （空数组无公共子数组）。 d = 0 时，退化为标准最长公共子数组问题。 逐步计算示例 以 nums1 = [1, 2, 3] , nums2 = [2, 3, 1] , k = 1 为例： 步骤1：初始化三维表 | d \ i,j | 0 | 1 | 2 | 3 | |---------|---|---|---|---| | d=0 | 0 | 0 | 0 | 0 | | d=1 | 0 | 0 | 0 | 0 | 步骤2：填充 d=0 （不允许删除） i=1, j=1 : nums1[0]=1 , nums2[0]=2 → 不匹配 → dp[1][1][0]=0 i=1, j=2 : 1 vs 3 → 0 i=2, j=1 : 2 vs 2 → 匹配 → dp[2][1][0] = dp[1][0][0] + 1 = 1 继续填充... 步骤3：填充 d=1 （允许删除1次） i=1, j=1 : 不匹配，删除 nums1 的 1 ： dp[0][1][0] + 1 = 1 删除 nums2 的 2 ： dp[1][0][0] + 1 = 1 取最大值 1 。 i=2, j=2 : nums1[1]=2 vs nums2[1]=3 不匹配 删除 nums1 的 2 ： dp[1][2][0] + 1 = 0+1=1 删除 nums2 的 3 ： dp[2][1][0] + 1 = 1+1=2 取最大值 2 。 步骤4：跟踪最长值 在计算过程中记录所有 dp[i][j][d] 的最大值。 算法优化 实际代码可优化为二维动态规划，通过滚动数组或状态压缩减少空间复杂度： 定义 dp[i][j] 为以 i 和 j 结尾的当前公共子数组长度，同时外层循环 d 并利用临时数组保存上一轮状态。 总结 本题通过扩展经典最长公共子数组的DP状态，引入删除次数的维度，灵活处理部分不匹配的情况。关键点在于状态转移时考虑删除操作的多种选择，并确保子数组的连续性在删除后依然成立。