双数组取首尾K次求最大得分 DP解法逻辑错误排查

问题描述 #

给定两个整数数组A和B，长度分别为N和M。初始得分为0，需要恰好执行K次操作。第i次操作（1-indexed）规则为：

• 从数组A或B的首部或尾部选择一个整数x，将其从对应数组中移除
• 将x的值累加到得分中

返回执行完K次操作后可获得的最大得分。

示例 #

输入：A = [3,1,2]，B = [2,8,1,9]，K=5
输出：24

解释：最优操作路径如下：

• 选择B尾部元素，得分加9，将9从B中移除
• 选择A首部元素，得分加3，将3从A中移除
• 选择B首部元素，得分加2，将2从B中移除
• 选择B首部元素，得分加8，将8从B中移除
• 选择A尾部元素，得分加2，将2从A中移除

总得分：9+3+2+8+2 = 24

约束条件 #

• 1 ≤ N ≤ 6000
• 1 ≤ M ≤ 6000
• 1 ≤ A[i] ≤ 10⁹
• 1 ≤ B[i] ≤ 10⁹
• 1 ≤ K ≤ N+M

我的解题思路 #

由于贪心策略（每次选择两数组四个端点的最大值）会在两端点值相等时出现决策冲突，无法得到正确结果，因此考虑枚举所有可能组合，且问题存在重叠子问题，因此选择动态规划（DP）求解。

对应的Python可复现代码如下：

A = [3,1,2]
N = len(A)

B = [2,8,1,9]
M = len(B)

K = 5

memo = {}

def solve(i,j, AL, BL):
    if (i,j,AL,BL) in memo:
        return memo[(i,j,AL,BL)]

    AR = (N-1)-(i-AL)
    BR = (M-1)-(j-BL)

    if AL>AR or BL>BR or i+j==K:
        return 0
    
    op1 = A[AL] + solve(i+1,j,AL+1,BL)
    op2 = B[BL] + solve(i,j+1,AL,BL+1)
    op3 = A[AR] + solve(i+1,j,AL,BL)
    op4 = B[BR] + solve(i,j+1,AL,BL)

    memo[(i,j,AL,BL)] = max(op1,op2,op3,op4)
    return memo[(i,j,AL,BL)]

print(solve(0,0,0,0))

状态定义说明：

• i表示已经从数组A中取了i个元素
• j表示已经从数组B中取了j个元素
• 已执行总操作数为i+j
• AL表示数组A当前剩余部分的左边界索引，即索引小于AL的元素已全部被取走；AR表示数组A当前剩余部分的右边界索引，即索引大于AR的元素已全部被取走
• BL表示数组B当前剩余部分的左边界索引，即索引小于BL的元素已全部被取走；BR表示数组B当前剩余部分的右边界索引，即索引大于BR的元素已全部被取走

每一步枚举四个可能的操作（取A左、取B左、取A右、取B右），选择结果最大的选项，同时使用记忆化存储已计算的状态避免重复计算。

疑问 #

该代码在多组测试用例上运行正确，但部分测试用例返回结果错误，报错类型为答案错误（Wrong Answer），不存在超时、内存超限、语法错误或运行时错误，说明代码仅存在逻辑层面的问题。

请帮忙找出会导致该解法失效的测试用例，并解释该解法出现逻辑错误的根本原因。

内容的提问来源于stack exchange，提问作者Rohit Singh