앨리스와 밥 두 사람이 있다고 가정하고 그들은 돌더미를 가지고 게임을 계속하고 있습니다. 여러 개의 말뚝이 일렬로 놓여 있고 각 말뚝은 배열 말뚝[i]에 양의 정수 개수의 돌을 가지고 있습니다. 게임의 목표는 가장 많은 돌로 끝나는 것입니다. 앨리스와 밥이 번갈아가며 앨리스가 먼저 출발합니다. 처음에는 M =1입니다. 각 플레이어의 차례에 해당 플레이어는 처음 X개의 남은 더미에 있는 모든 돌을 가져올 수 있습니다(여기서 1 <=X <=2M). 그런 다음 M =max(M, X)로 설정합니다. 돌이 남지 않으면 게임이 종료됩니다. 따라서 더미 =[2,7,9,4,4]이면 출력은 10이 됩니다. 이것은 Alice가 처음에 한 더미를 가져오고 Bob이 두 더미를 가져간 다음 Alice가 다시 2 더미를 가져오기 때문입니다. 앨리스는 2 + 4 + 4 =총 10개의 더미를 손에 넣을 수 있습니다. Alice가 처음에 두 개의 더미를 가져갔다면 Bob은 남은 세 개의 더미를 모두 가져갈 수 있습니다. 이 경우 앨리스는 2 + 7 =9 더미를 얻습니다. 따라서 더 크기 때문에 10을 반환합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 배열, i, m 및 dp라는 행렬 하나를 사용하는 solve라는 재귀 함수 하나를 만듭니다.
- i>=arr의 크기이면 0을 반환합니다.
- dp[i, m]이 -1이 아니면 dp[i, m]을 반환
- i – 1 + 2m>=배열의 크기이면 arr[i]를 반환합니다.
- op :=inf
- 1 ~ 2m 범위의 x에 대해
- op :=op의 최소값, solve(arr, i + x, x와 m의 최대값, dp)
- dp[i, m] :=arr[i] – 연산
- dp[i, m]를 반환
- 실제 방법은 다음과 같습니다 -
- n :=파일 배열의 크기, 크기가 n인 arr이라는 배열 하나를 만듭니다.
- arr[n - 1] :=더미[n – 1]
- i:=n – 2에서 0까지
- arr[i] :=arr[i + 1] + 더미[i]
- 크기 (n + 1) x (n + 1)의 행렬 하나를 만들고 이것을 -1로 채웁니다.
- 리턴 풀이(arr, 0, 1, dp)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void printVector(vector <int> v){
for(int i =0;i<v.size();i++)cout << v[i] << " ";
cout << endl;
}
int stoneGameII(vector<int>& piles) {
int n = piles.size();
vector <int> arr(n);
arr[n-1] = piles[n-1];
for(int i = n-2;i>=0;i--)arr[i] = arr[i+1] + piles[i];
vector < vector <int> > dp(n+1,vector <int> (n+1,-1));
return solve(arr,0,1,dp);
}
int solve(vector <int> arr, int i, int m, vector < vector <int> > &dp){
if(i >=arr.size())return 0;
if(dp[i][m]!=-1)return dp[i][m];
if(i-1+2*m >=arr.size())return arr[i];
int opponentCanTake = INT_MAX;
for(int x =1;x<=2*m;x++){
opponentCanTake = min(opponentCanTake,solve(arr,i+x,max(x,m),dp));
}
dp[i][m] = arr[i] - opponentCanTake;
return dp[i][m];
}
};
main(){
vector<int> v = {2,7,9,4,4};
Solution ob;
cout <<(ob.stoneGameII(v));
} 입력
[2,7,9,4,4]
출력
10