Giả sử có hai người Alice và Bob, họ đang tiếp tục trò chơi với đống đá. Có một số cọc được đặt thành một hàng, và mỗi cọc có một số nguyên dương đá trong một cọc mảng [i]. Mục tiêu của trò chơi là kết thúc với nhiều viên đá nhất. Alice và Bob thay phiên nhau, Alice bắt đầu trước. Ban đầu, M =1. Trong mỗi lượt của người chơi, người chơi đó có thể lấy tất cả các viên đá trong X cọc đầu tiên còn lại, ở đây 1 <=X <=2M. Sau đó, ta đặt M =max (M, X). Trò chơi kết thúc khi không còn viên đá nào. Vì vậy, nếu cọc =[2,7,9,4,4], thì đầu ra sẽ là 10. Điều này là do nếu Alice lấy một cọc lúc đầu, sau đó Bob lấy hai cọc, sau đó Alice lại lấy 2 cọc. Alice có thể nhận được tổng cộng 2 + 4 + 4 =10 cọc trong tay. Nếu Alice lấy hai cọc lúc đầu, thì Bob có thể lấy cả ba cọc còn lại. Trong trường hợp này, Alice nhận được 2 + 7 =9 cọc. Vì vậy, chúng tôi sẽ nhận được lợi nhuận 10 vì nó lớn hơn.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Tạo một hàm đệ quy có tên là giải quyết, hàm này sẽ nhận mảng, i, m và một ma trận được gọi là dp.
- if i> =size of arr, thì trả về 0
- nếu dp [i, m] không phải là -1, thì trả về dp [i, m]
- if i - 1 + 2m> =size of array, thì trả về arr [i]
- op:=inf
- cho x trong phạm vi từ 1 đến 2m
- op:=tối thiểu trong số op, giải quyết (arr, i + x, tối đa của x và m, dp)
- dp [i, m]:=arr [i] - op
- trả về dp [i, m]
- phương pháp thực tế sẽ như thế nào -
- n:=kích thước của mảng cọc, tạo một mảng được gọi là arr có kích thước n
- arr [n - 1]:=cọc [n - 1]
- for i:=n - 2 xuống 0
- arr [i]:=arr [i + 1] + cọc [i]
- tạo một ma trận có kích thước (n + 1) x (n + 1) và điền vào ma trận này bằng -1
- trả về giải quyết (arr, 0, 1, dp)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
[2,7,9,4,4]
Đầu ra
10