동적 프로그래밍에 대한 무차별 대입 재귀(Dynamic Programming Attempt Models on Scope) 02

주제

솔루션 #1 무차별 대입 재귀

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 메모라이즈 검색

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;
    }

솔루션 #3 동적 프로그래밍

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]);
    }