最大拿牌的得分

假设有个游戏，一列牌有不同分数，但是只能从两头拿 ，拿到最后分数最高的人获胜，假设两个人都是聪明人，求最后的最高分是多少？

思路：递归算法，一个人拿左边牌，另一个人的得分 和拿右边牌 另一个人的得分作比较，只拿让对方得分最小的牌，反过来也是一样，那如果轮到对方拿牌自己也将会拿到最小的分，

两个方法，分别代表A 的最大得分 B的最大得分

private  static int getAMaxPoker(int []arr, int first, int end, boolean aFirst,int total){
        if(first==end){
            if(aFirst) {
                return arr[first];
            }else{
                return 0;
            }
        }
        if(aFirst) {
            int left = arr[first];
            int otherleft = getAMaxPoker(arr, first + 1, end, false,total-left);
            int right = arr[end];
            int otherright = getAMaxPoker(arr, first, end - 1,false,total-right);
            int lefttotal=left+otherleft;
            int righttotal=right+otherright;
            if(lefttotal>righttotal){
                return lefttotal;
            }else{
                return righttotal;
            }
        }else{
           return total- getBMaxPoker(arr,first,end,true,total);
        }
    }

private  static int getBMaxPoker(int []arr, int first, int end, boolean bFirst,int total) {
        if (first == end) {
            if (bFirst) {
                return arr[first];
            } else {
                return 0;
            }
        }
        if (bFirst) {
            int left = arr[first];
            int otherleft = getBMaxPoker(arr, first + 1, end, false,total-left);
            int right = arr[end];
            int otherright = getBMaxPoker(arr, first, end - 1, false,total-right);
            if (left + otherleft > right + otherright) {
                return left + otherleft;
            } else {
                return right + otherright;
            }
        }else{
            return total-getAMaxPoker(arr,first,end,true,total);
        }
    }

测试方法：

public static void main(String[] args) {
        int []arr={1,100,2};
        int sum=0;
        for (int i = 0; i < arr.length; i++) {
            sum+=arr[i];
        }
        int maxPoker = getAMaxPoker(arr, 0, arr.length - 1, true,sum);
        System.out.println((sum-maxPoker)>maxPoker?(sum-maxPoker):maxPoker);

    }

原文地址：https://blog.csdn.net/weixin_42531583/article/details/145099113

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！