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

4004 단어 leetcodealgorithms

주제



정수 배열이 주어지면 서로 다른 값을 나타내는 카드가 일렬로 정렬됩니다. 플레이어 A와 플레이어 B가 차례로 각 카드를 가져갑니다. 플레이어 A가 먼저 가져오고 플레이어 B가 나중에 가져가도록 규정되어 있습니다. 하지만 각 플레이어는 한 번에 가장 왼쪽 또는 가장 오른쪽 카드만 가져갈 수 있습니다.플레이어 A와 플레이어 B 모두 매우 영리합니다.최종 승자의 점수를 돌려주세요.

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


  • 매개변수를 결정하고, 플레이어는 [L-R] 배열 범위에서 카드를 선택하고 [L] 또는 [R] 위치의 카드만 선택할 수 있습니다.
  • 기본 사례를 찾습니다. Palyer A가 먼저 카드를 가져옵니다. L == R이면 카드가 한 장만 남아 있으며 플레이어 A가 직접 가져갈 수 있습니다. Palyer B는 나중에 카드를 가져옵니다. L == R이면 남은 카드가 없다는 의미입니다.
  • 플레이어 A는 한 번에 가장 왼쪽 또는 가장 오른쪽 카드만 가져갈 수 있으며 다음 카드를 가져오는 최선의 방법을 판단해야 합니다. 2개 중 결과가 가장 좋은 것을 선택하십시오.

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

    좋은 웹페이지 즐겨찾기