我正在用 Java 进行动态编程任务，但我陷入了困境： 在任务中，我们会得到一系列桶，里面有随机数量的岩石，两个玩家从一开始就知道它们的数量。玩家进行游览并从侧面挑选一个边界桶：
桶：(3)(3)(8)(2)(10)(4)
P1：还剩（3）个桶：（3）（8）（2）（10）（4），
P2：还剩（4）个桶：（3）（8）（2）（10），
P1：还剩（10）个桶：（3）（8）（2），
P2(3) 桶剩余：(8)(2)，
P1：还剩（8）个桶（2），
P2:(2)结束
最终分数的计算方式为（玩家 1 的石头）-（玩家 2 的石头）
分数 = (3+10+8)-(4+3+2) = 12
我们玩玩家 1，我们的目标是找到我们得分最高的最佳选择顺序。
我知道DP的概念，但我不知道我可以节省什么来缩短时间。 我用 minmax 算法完成的代码的主要部分并且它有效，但我不知道如何将它与动态编程结合起来
我尝试使用一个矩阵，其中行作为左侧的存储桶，列作为右侧的存储桶，因此当我们使用数组的相同“部分”时，我可以保存答案，但我遇到了一些问题...
EDIT1：添加了我的代码
public int maxGain(int[] values)
{
this.moves = new int[values.length+1][values.length+1];
return _maxGain(values,0,values.length-1,0,0,values.length,true,0,0);
}
public int _maxGain(int[] values, int leftBowl, int rightBowl, int valuePlayer1, int valuePlayer2,int leftBowls, boolean ifFirstPlayer, int leftMoves, int rightMoves){
//Check if end of the game
if(leftBowls == 0) {
//Calculate the final score
return valuePlayer1 - valuePlayer2;
}
//System.out.println("Left:"+values[leftBowl]+", right: "+values[rightBowl]);
// If first player
if(ifFirstPlayer){
int maxEval = Integer.MIN_VALUE;
int eval;
for(int i=0;i<2;i++){
if(i==0){
//Do move
valuePlayer1 = valuePlayer1+values[leftBowl];
leftBowls--;
leftMoves++;
if(moves[leftMoves][rightMoves] != 0){
eval = moves[leftMoves][rightMoves];
System.out.println("USED! Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
}else {
eval = _maxGain(values, leftBowl + 1, rightBowl, valuePlayer1, valuePlayer2, leftBowls, false, leftMoves, rightMoves);
moves[leftMoves][rightMoves] = eval;
System.out.println("Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
for(int x=0;x<this.moves.length;x++){
for(int j=0;j<this.moves.length;j++){
System.out.print(this.moves[x][j]+" ");
}
System.out.println();
}
}
leftMoves--;
maxEval = Math.max(maxEval,eval);
//Undo move
valuePlayer1 = valuePlayer1-values[leftBowl];
leftBowls++;
}else{
//Do move
valuePlayer1 = valuePlayer1+values[rightBowl];
leftBowls--;
rightMoves++;
if(moves[leftMoves][rightMoves] != 0){
eval = moves[leftMoves][rightMoves];
System.out.println("USED! Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
}else {
eval = _maxGain(values, leftBowl, rightBowl - 1, valuePlayer1, valuePlayer2, leftBowls, false, leftMoves, rightMoves);
moves[leftMoves][rightMoves] = eval;
System.out.println("Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
for(int x=0;x<this.moves.length;x++){
for(int j=0;j<this.moves.length;j++){
System.out.print(this.moves[x][j]+" ");
}
System.out.println();
}
}
rightMoves--;
maxEval = Math.max(maxEval,eval);
//Undo move
valuePlayer1 = valuePlayer1-values[rightBowl];
leftBowls++;
}
}
return maxEval;
//If second player
}else{
int minEval = Integer.MAX_VALUE;
int eval;
for(int i=0;i<2;i++){
if(i==0){
//Do move
valuePlayer2 = valuePlayer2+values[leftBowl];
leftBowls--;
leftMoves++;
if(moves[leftMoves][rightMoves] != 0){
eval = moves[leftMoves][rightMoves];
System.out.println("USED! Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
}else {
eval = _maxGain(values, leftBowl + 1, rightBowl, valuePlayer1, valuePlayer2, leftBowls, true, leftMoves, rightMoves);
moves[leftMoves][rightMoves] = eval;
System.out.println("Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
for(int x=0;x<this.moves.length;x++){
for(int j=0;j<this.moves.length;j++){
System.out.print(this.moves[x][j]+" ");
}
System.out.println();
}
}
leftMoves--;
minEval = Math.min(minEval,eval);
//Undo move
valuePlayer2 = valuePlayer2-values[leftBowl];
leftBowls++;
}else{
//Do move
valuePlayer2 = valuePlayer2+values[rightBowl];
leftBowls--;
rightMoves++;
if(moves[leftMoves][rightMoves] != 0){
eval = moves[leftMoves][rightMoves];
System.out.println("USED! Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
}else {
eval = _maxGain(values, leftBowl, rightBowl - 1, valuePlayer1, valuePlayer2, leftBowls, true, leftMoves, rightMoves);
moves[leftMoves][rightMoves] = eval;
System.out.println("Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
for(int x=0;x<this.moves.length;x++){
for(int j=0;j<this.moves.length;j++){
System.out.print(this.moves[x][j]+" ");
}
System.out.println();
}
}
rightMoves--;
minEval = Math.min(minEval,eval);
//Undo move
valuePlayer2 = valuePlayer2-values[rightBowl];
leftBowls++;
}
}
return minEval;
}
}
好的，我在 Github 上找到了此类任务的代码， 如果其他人以后需要的话我会把它留给他们：
0
我正在用 Java 进行动态编程任务，但我陷入了困境：在任务中，我们得到了一个桶数组，里面有随机数量的岩石，两个玩家从一开始就知道它们的数量。玩家进行游览并从侧面挑选一个边界桶：
桶：(3)(3)(8)(2)(10)(4)
P1：还剩（3）个桶：（3）（8）（2）（10）（4），
P2：还剩（4）个桶：（3）（8）（2）（10），
P1：还剩（10）个桶：（3）（8）（2），
P2(3) 桶剩余：(8)(2)，
P1：还剩（8）个桶（2），
P2:(2)结束
最终分数的计算方式为（玩家 1 的石头）-（玩家 2 的石头）
分数 = (3+10+8)-(4+3+2) = 12
我们玩玩家 1，我们的目标是找到我们得分最高的最佳选择顺序。
我知道DP的概念，但我不知道我可以节省什么来缩短时间。我用 minmax 算法完成的代码的主要部分并且它有效，但我不知道如何将它与动态编程结合起来
我尝试使用一个矩阵，其中行作为左侧的存储桶，列作为右侧的存储桶，这样当我们使用数组的相同“部分”时，我可以保存答案，但我遇到了一些问题...