Brute force recursion to dynamic programming(Dynamic Programming Attempt Models on Scope) 02

Topic

Given an integer array, the cards representing differeent values are arranged in a line.Player A and Player B take each card in turn.It is stipulated that player A takes it first, and player B takes it later. But each player can only take the leftmost or rightmost card at time.Both Player A and Player B are extremely smart.Please return the score of the final winner.

Solution #1 Brute force recursion

1. Determine the parameters, palyers can choose a card from the [L-R] range of array, and only select cards in the [L] or [R] position.

2. Find base case. Palyer A takes cards first, when L == R, it means that there is only one card left, and player A can take it directly. Palyer B takes cards later, when L == R, it means that there are no cards left.

3. Player A can only take the leftmost or rightmost card at time and need to judge the best way to take the next card. Select the one with the best result out of two.
   

public static int myWin1(int[] arr) {
        int first = myF1(arr, 0, arr.length - 1);
        int second = myG1(arr, 0, arr.length - 1);
        return Math.max(first, second);
    }

    public static int myF1(int[] arr, int L, int R) {
        // player A take cards first
        if (L == R) {
            return arr[L];
        }
        int p1 = arr[L] + myG1(arr, L + 1, R); // current select arr[L] and the range can be selected next is arr[L+1...R]
        int p2 = arr[R] + myG1(arr, L, R - 1);// current select arr[R] and the range can be selected next is arr[L...R-1]
        // select the max
        return Math.max(p1, p2);
    }

    private static int myG1(int[] arr, int L, int R) {
        // player B take cards later
        if (L == R) {
            return 0;
        }
        int p1 = myF1(arr, L + 1, R);// player A took the card in [L] position
        int p2 = myF1(arr, L, R - 1);// player A took the card in [R] position
        // return the min. means that player B took the largest card and left player A with the smallest.
        return Math.min(p1, p2);
    }

Solution #2 Memoized search

public static int myWin2(int[] arr) {
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                fmap[i][j] = -1;
                gmap[i][j] = -1;
            }
        }
        int first = myF2(arr, 0, arr.length - 1, fmap, gmap);
        int second = myG2(arr, 0, arr.length - 1, fmap, gmap);
        return Math.max(first, second);
    }

    public static int myF2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {

        if (fmap[L][R] != -1) {
            return fmap[L][R];
        }
        int ans = 0;
        if (L == R) {
            ans = arr[L];
        } else {
            int p1 = arr[L] + myG2(arr, L + 1, R, fmap, gmap);
            int p2 = arr[R] + myG2(arr, L, R - 1, fmap, gmap);
            ans = Math.max(p1, p2);
        }
        fmap[L][R] = ans;
        return ans;
    }

    private static int myG2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
        if (gmap[L][R] != -1) {
            return gmap[L][R];
        }
        int ans = 0;
        if (L != R) {
            int p1 = myF2(arr, L + 1, R, fmap, gmap);
            int p2 = myF2(arr, L, R - 1, fmap, gmap);
            ans = Math.min(p1, p2);
        }
        gmap[L][R] = ans;
        return ans;
    }

Solution #3 Dynamic programming

public static int myWin3(int[] arr) {
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for (int i = 0; i < N; i++) {
            fmap[i][i] = arr[i];
        }
        for (int startCol = 1; startCol < N; startCol++) {
            int L = 0;
            int R = startCol;
            while (R < N) {
                fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
                gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]);
                L++;
                R++;
            }
        }
        return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
    }