任何人都可以解釋這個memoization /動態編程概率/解謎？

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和right - left之間。從左側

Example: 
4 -10 -20 7 

採取：

表[1] [4] = MAX（總和（1,1） - 表[2] [4]，和（1,2） - 表[3] [4]， sum（1,3） - 表[4] [4]，sum（1,4））。從右側

採取：

表[1] [4] = MAX（總和（4,4） - 表[1] [3]，和（3,4） - 表[1] [2]， sum（2,4） - 表[1] [1]，sum（1,4））。

sum(L, R)是數字陣列L和R之間的總和。我正在減去，因爲下一個對手回合。