Violence recursion to dynamic programming 02 (very clever game of CARDS)

1.题目

What is super smart,such as assignments 50 100 20 10 ,Extremely smart people choose first hand10,Then it doesn't matter which one you choose,This first mover can get it100,Finally get the maximum sum,成为赢家

2. 暴力递归

递归终止条件,If only the last card is left,Take it first,If it is backhand,则为0,Because it was taken first
每次会从 最左边 和 Maximum backhand 之和 与 最右边 和 Maximum backhand 之和 取较大值
After taking it first,The backhand becomes the forehand,The current value of the second hand is the smaller value left by the previous hand.

    public int cardsInLine(int[] arr) {
    
        //如果无值
        if (arr == null || arr.length == 0) {
    
            return -1;
        }
        //Returns the winner's score
        return Math.max(first(arr, 0, arr.length - 1), second(arr, 0, arr.length - 1));
    }

    //先手
    private int first(int[] arr, int left, int right) {
    
        //If only the last card is left,Take it first,No backhand
        if (left == right) {
    
            return arr[left];
        }
        //The first player takes the maximum value from the cards 50 100 20 10
        //If you take it first50,Only get it the second time10 60
        int leftCard = arr[left] + second(arr, left + 1, right);
        //If you take it first10,Only get it the second time100 110
        int rightCard = arr[right] + second(arr, left, right - 1);
        //Returns the maximum value that can be selected by the first mover
        return Math.max(leftCard, rightCard);
    }

    //后手
    public int second(int[] arr, int left, int right) {
    
        //No cards in the back
        if (left == right) {
    
            return 0;
        }
        //No need to add back arr[left] arr[right] 他没得选择
        //At this time, the back hand became the first hand
        int leftCard = first(arr, left + 1, right);
        int rightCard = first(arr, left, right - 1);
        //这个返回值,It's for the first mover,Because the current backhand will leave you a small one
        return Math.min(leftCard, rightCard);
    }

3. 动态规划

    public int cardsInLine2(int[] arr) {
    
        //如果无值
        if (arr == null || arr.length == 0) {
    
            return -1;
        }
        int n = arr.length;
        //Starter array
        int[][] firstArr = new int[n][n];
        //backhand array
        int[][] secondArr = new int[n][n];
        //Initialized to when no value is filled-1
        for (int i = 0; i <n ; i++) {
    
            for (int j = 0; j <n ; j++) {
    
                firstArr[i][j] = -1;
                secondArr[i][j] = -1;
            }
        }
        //Returns the winner's score
        return Math.max(first2(arr, 0, arr.length - 1, firstArr, secondArr), second2(arr, 0, arr.length - 1, firstArr, secondArr));
    }


    private int first2(int[] arr, int left, int right, int[][] firstArr, int[][] secondArr) {
    
        //If the element at this position has already been calculated,Returns the current element directly
        if (firstArr[left][right] != -1) {
    
            return firstArr[left][right];
        }
        //If there is only one card
        if (left == right) {
    
            firstArr[left][right] = arr[left];
            return firstArr[left][right];
        }
        //否则计算
        int getLeft = arr[left] + second2(arr, left + 1, right, firstArr, secondArr);
        int getRight = arr[right] + second2(arr, left, right - 1, firstArr, secondArr);
        firstArr[left][right] = Math.max(getLeft, getRight);
        return firstArr[left][right];
    }

    private int second2(int[] arr, int left, int right, int[][] firstArr, int[][] secondArr) {
    
        if (secondArr[left][right] != -1) {
    
            return secondArr[left][right];
        }
        //If there is only one card
        if (left == right) {
    
            secondArr[left][right] = 0;
            return secondArr[left][right];
        }
        //The backhand is now the first mover,取值
        int getLeft =first2(arr, left+1, right, firstArr, secondArr);
        int getRight = first2(arr, left, right-1, firstArr, secondArr);
        secondArr[left][right] = Math.min(getLeft, getRight);
        return secondArr[left][right];
    }

4. 动态规划优化

    public int cardsInLine3(int[] arr) {
    
        //如果无值
        if (arr == null || arr.length == 0) {
    
            return -1;
        }
        int n = arr.length;
        //Starter array
        int[][] firstArr = new int[n][n];
        //backhand array
        int[][] secondArr = new int[n][n];
        //The choice when initializing the diagonal element of the first hand array to the last card,The backhand group is 0
        for (int i = 0; i <n ; i++) {
    
            firstArr[i][i] = arr[i];
        }
        // L为横,R为纵
        //The two 2D arrays use only the upper right corner,因为 L<=RHorizontally established
        // firstArr[0][0]已经赋值过了
        for (int i = 1; i < n; i++) {
    
            int left = 0;
            int right = i;
            while (right < n) {
    
                firstArr[left][right] = Math.max(arr[left] + secondArr[left + 1][right], arr[right] + secondArr[left][right - 1]);
                secondArr[left][right] = Math.min(firstArr[left + 1][right], firstArr[left][right - 1]);
                left++;
                right++;
            }
        }
        //Returns the winner's score
        return Math.max(firstArr[0][n-1],secondArr[0][n-1]);
    }

    public static void main(String[] args) {
    
        System.out.println(new CardsInLine().cardsInLine(new int[]{
    5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7}));
        System.out.println(new CardsInLine().cardsInLine2(new int[]{
    5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7}));
        System.out.println(new CardsInLine().cardsInLine3(new int[]{
    5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7}));
    }