동적 프로그래밍에 대한 무차별 대입 재귀(Dynamic Programming Attempt Models on Scope) 02
4004 단어 leetcodealgorithms
주제
정수 배열이 주어지면 서로 다른 값을 나타내는 카드가 일렬로 정렬됩니다. 플레이어 A와 플레이어 B가 차례로 각 카드를 가져갑니다. 플레이어 A가 먼저 가져오고 플레이어 B가 나중에 가져가도록 규정되어 있습니다. 하지만 각 플레이어는 한 번에 가장 왼쪽 또는 가장 오른쪽 카드만 가져갈 수 있습니다.플레이어 A와 플레이어 B 모두 매우 영리합니다.최종 승자의 점수를 돌려주세요.
솔루션 #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]);
}
Reference
이 문제에 관하여(동적 프로그래밍에 대한 무차별 대입 재귀(Dynamic Programming Attempt Models on Scope) 02), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/caixr/brute-force-recursion-to-dynamic-programmingdynamic-programming-attempt-models-on-scope-02-j9h텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)