java - 具有动态规划问题的桶数组

Question

我正在用 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;
        }
    }

Answer 1

好的，我在 Github 上找到了此类任务的代码，如果其他人以后需要的话我会把它留给他们:

https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/NPotGold.java?fbclid=IwAR2PZ8MvNJcQmlU13wj1n_c6m1UhQY7FXAY07RwaI6wOOXAMgDOVRxFahD0