谁能解释一下这个记忆/动态编程问题/谜题的解决方案？

Question

这是问题陈述：

这是一个两人游戏。最初，数组中有 n 个整数，玩家 A 和 B 有机会交替取它们。每个玩家可以从数组的左端或右端取一个或多个数字，但不能同时从两端取。在他的时间内，他可以随心所欲地获取任意数量的连续数字。当玩家从数组中取出所有数字时，游戏结束。每个玩家的分数是通过他所获得的数字的总和来计算的。每个玩家都试图从其他玩家那里获得更多分数。如果双方都发挥最佳，并且玩家 A 开始游戏，那么玩家 A 可以比玩家 B 多获得多少分？

输入

输入由多个案例组成。每种情况都以指定整数 n (0 < n ≤100) 的行开头，即数组中的元素数量。之后，给出游戏的n个号码。输入以 n=0 行终止。

输出

对于每个测试用例，打印一个数字，该数字代表第一个玩家在最佳地玩这个游戏后获得的最大差异。

Sample Input                                Output for Sample Input

4

4 -10 -20 7                                 7

4

1 2 3 4                                     10

5

4 -10 -20 7 19                              12

0

这就是这个问题的解决方案。

#include<stdio.h>
#include<stdlib.h>
#define maxn 103

//typedef long long bg;
typedef long bg;

bg Table[maxn][maxn];
bg Seq[maxn];
bool Flag[maxn][maxn];
bg N;

bg Sum(int l, int r) {
    int i, sum = 0;
    for (i = l; i <= r; i++)
        sum += Seq[i];
    return sum;
}

bg Recur(int L, int R) {
    bg max, i, d, k;
    if (L == R)
        return Seq[L];
    if (Flag[L][R])
        return Table[L][R];
    max = Sum(L, R);
    d = Seq[L];
    for (i = L + 1; i <= R; i++) {
        k = Recur(i, R);
        if ((d - k) > max)
            max = d - k;
        d += Seq[i];
    }
    d = Seq[R];
    for (i = R - 1; i >= L; i--) {
        k = Recur(L, i);
        if ((d - k) > max)
            max = d - k;
        d += Seq[i];
    }
    Flag[L][R] = true;
    Table[L][R] = max;
    return max;
}

void Cal() {
    bg max, i, d, k;
    max = Sum(1, N);
    d = Seq[1];
    for (i = 2; i <= N; i++) {
        k = Recur(i, N);
        if ((d - k) > max)
            max = d - k;
        d += Seq[i];
    }
    d = Seq[N];
    for (i = N - 1; i >= 1; i--) {
        k = Recur(1, i);
        if ((d - k) > max)
            max = d - k;
        d += Seq[i];
    }
    printf("%ld\n", max);
}

void Reset() {
    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j <= 100; j++)
            Flag[i][j] = false;
    }
}
int main() {
    //freopen("in.txt", "r", stdin);
    int i;
    while (scanf("%ld", &N) && N) {
        for (i = 1; i <= N; i++)
            scanf("%ld", &Seq[i]);
        Cal();
        Reset();
    }
    return 0;
}

我确实调试了它，但发现很难理解解决方案。

谁能解释一下这个问题的代码或解决方案。或者任何人都可以发布代码来用动态编程而不是递归来解决这个问题？

Answer 1

这里的状态是 Table[left][right]，如果您有一个包含从 left 到 right 的元素的序列，它代表最佳解决方案包容性。在每一步中都会尝试每种可能的移动 - 从左侧获取 N 个元素或从右侧获取 N 个元素，其中 N 介于 1 和 <代码>右 - 左。

Example:
4 -10 -20 7

从左边看：

表[1][4] = max(sum(1, 1) - 表[2][4], sum(1, 2) - 表[3][4],
sum(1, 3) - 表[4][4], sum(1, 4))。

从右边开始：

表[1][4] = max(sum(4, 4) - 表[1][3], sum(3, 4) - 表[1][2],
sum(2, 4) - 表[1][1], sum(1, 4))。

sum(L, R) 是 L 和 R 之间的数组编号之和。我因为下一个对手回合而减去。