I’m doing a task with dynamic programming in Java and I got stuck: In the task we are given an array of buckets with random number of rocks inside, where both players know their amount from the start. Players take tours and pick one border bucket from the sides:
Buckets: (3)(3)(8)(2)(10)(4)
P1: (3) buckets left: (3)(8)(2)(10)(4),
P2:(4) buckets left: (3)(8)(2)(10),
P1:(10) buckets left: (3)(8)(2),
P2(3) buckets left: (8)(2),
P1:(8) buckets left (2),
P2:(2) end
Final score is calculated with (rocks of player 1) - (rocks of player2)
Score = (3+10+8)-(4+3+2) = 12
We play player1 and our goal is to find the OPTIMAL pick order in which we have the biggest score.
I know the concept of DP but I have no idea what could I save in order to improve the time. The main part of the code I did with minmax algorithm and it worked but I have no idea how to combine it with dynamic programming
I tried having a matrix with rows as buckets from left and columns as buckets from right, so I can save there answers for when we use the same “part” of the array, but I had some problems with it...
EDIT1: added my code
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;
}
}
Ok, so I have found on Github the code for exactly this type of task, I will leave it for other people if they need it later: