用动态规划技术调试Google KickStart "2022“圆D最大增益问题

Question

我是解决Google KickStart 2022回合D-最大增益问题通过动态编程技术，但我厌倦了调试它。

以下是问题的链接：最大增益问题

下面是我的python代码：

#supporting function
def proceedForOneOnly(O, k, gainOne):
    if k==0:
        return 0
    return gainOne + max([proceedForOneOnly(O[1:], k-1, O[0]), proceedForOneOnly(O[:-1], k-1, O[-1])])

#solve
def maxGain(A, B, k, gain):
    #BaseCase
    if k==0:
        return 0
    #Checking if any of the two task-arrays are empty
    if len(B)==0:
        return proceedForOneOnly(A, k-1, gain)
    elif len(A)==0:
        return proceedForOneOnly(B, k-1, gain)
    #if both aren't empty
    return gain + max([maxGain(A[1:], B, k-1, A[0]), maxGain(A[:-1], B, k-1, A[-1]), maxGain(A, B[1:], k-1, B[0]), maxGain(A, B[:-1], k-1, B[-1])])

#taking input and caling maxGain() iteratively
def main():
    n = int(input())
    for i in range(n):
        nA = int(input()); A = list(map((lambda i: int(i)), input().split()))
        nB = int(input()); B = list(map((lambda i: int(i)), input().split()))
        k  = int(input())
        print(f"Case #{1}: {maxGain(A, B, k, 0)}")

main()

问题是，我得到了前两个测试用例的输出22 (应该是24)和138 (应该是148)，这两个测试用例附在下面：

2
3
3 1 2
4
2 8 1 9
5
4
1 100 4 3
6
15 10 12 5 1 10
6

，谁能帮我弄清楚出什么事了吗？

Answer 1

我觉得你的循环少了一次。

但是，运行它仍然需要很长的时间，但是如果您可以在主调用中传递k+1而不是k，这对我是有用的。

不错的方法。

将努力改善这一状况