收集保持在一条线上时总价值最大的卡片（仅从角落提取）

Question

考虑以下游戏。

一位庄家发出了一系列 s1 ...sn 牌，面朝上，其中每张卡片 si 都有一个值 vi。然后两名玩家轮流从序列中挑选一张牌，但是只能挑选（剩余）序列的第一张或最后一张牌。目标是收集卡片总价值最大。（例如，你可以把卡片想象成不同面额的钞票。）

给出一个复杂度为 O(n^2) 的算法来计算第一个玩家的最优策略（只是最大可获得的代码）。

我试过顺路解决它，可能解决了这是我的代码... 数组卡片具有每张卡片的值。卡片的第 0 个元素未使用且浪费（基本索引 1）！

  #include<bits/stdc++.h>
  using namespace std;
  int main()
  {
   int cards[]={0,2,100,101,1};
   int n=4;
   int i,j,l,sum=204;
   int dp[n+1][n+1];
   memset(dp,0,sizeof(dp));
   for(i=1;i<=n;i++)
      dp[i][i]=cards[i];
   for(l=2;l<=n;l++)
   {
      for(i=1;i<=n-l+1;i++)
              {
                  j=i+l-1;
                  dp[i][j]=max(cards[i]-dp[i+1][j],cards[j]-dp[i][j-1]);
               }
    }
    printf("%d\n",(sum+dp[1][n])/2);

    return 0;
    }

在最后的打印语句中，我打印了(sum+dp[1][n])/2，因为元素是2n，所以当我做这个操作时，n将被包括在内，其余的n将被减去，我得到包含值的总和。

虽然它给出了正确答案，但我仍然无法说出 dp[i][j] 到底代表什么！！它不代表可获得的最大价值（因为它不会直接给我那个价值）。那么我的另一个问题是什么意思？？

有没有其他思路可以解决这样的问题？

Answer 1

在您发布的代码中，dp[i][j] 代表第一个和第二个玩家可以从子字符串 i..j 开始获得的最大点数差异：dp[i][j]=max(first[i][j]-second[i][j])（这是不是编程语言公式，只是为了给出想法），这里我们称第一个玩家为从该位置开始的玩家。

所以考虑一个子串i..j。第一个玩家 (A) 可以选择拿第一张或最后一张牌。如果他拿了第一张牌，他会得到 cards[i]，但是他的对手 (B) 将从子串 i+1..j 开始。他会竭尽全力，在他的人情中得到差价dp[i+1][j]，也就是差价会pointsB - pointsA = dp[i+1][j]。但是对于我们的位置i,j，我们对差异pointsA-pointsB感兴趣，所以我们取-dp[i+1][j]并记住取的card[i]，因此

dp[i][j]=card[i]-dp[i+1][j]

还有一种变体，就是取最后一张牌，结果为

dp[i][j]=card[j]-dp[i][j+1]

显然，玩家会选择最好的选项，因此您应该取两个值中的最大值。

收集保持在一条线上时总价值最大的卡片（仅从角落提取）

Collect cards of largest total value when kept in a line (extraction only from the corners)

c++

algorithm

dynamic-programming