สมมติว่ามีสองคนที่อลิซและบ็อบ พวกเขากำลังเล่นเกมต่อด้วยกองหิน มีกองจำนวนหนึ่งวางเรียงเป็นแถว และแต่ละกองมีจำนวนเต็มบวกของหินในกองอาร์เรย์[i] เป้าหมายของเกมคือการจบด้วยหินมากที่สุด อลิซและบ็อบผลัดกัน โดยอลิซเริ่มก่อน เริ่มแรก M =1 ในเทิร์นของผู้เล่นแต่ละคน ผู้เล่นนั้นสามารถเอาหินทั้งหมดในกอง X อันแรกที่เหลืออยู่ที่นี่ 1 <=X <=2M จากนั้นเราตั้งค่า M =สูงสุด (M, X) เกมจะจบลงเมื่อไม่มีก้อนหินเหลืออยู่ ดังนั้นหากกอง =[2,7,9,4,4] ผลลัพธ์จะเป็น 10 นี่เป็นเพราะถ้าอลิซรับหนึ่งกองในตอนเริ่มต้น บ็อบก็จะรับสองกอง แล้วอลิซก็จะรับอีก 2 กอง อลิซสามารถรับ 2 + 4 + 4 =10 กองทั้งหมดในมือของเธอ ถ้าอลิซรับสองกองในตอนเริ่มต้น บ็อบก็สามารถรับทั้งสามกองที่เหลือได้ ในกรณีนี้ อลิซได้ 2 + 7 =9 กอง ดังนั้นเราจะได้ผลตอบแทน 10 เนื่องจากมีขนาดใหญ่
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างฟังก์ชันเรียกซ้ำหนึ่งฟังก์ชันที่เรียกว่า Solve ซึ่งจะรับอาร์เรย์ i, m และเมทริกซ์หนึ่งตัวที่เรียกว่า dp
- ถ้า i>=ขนาดของ arr ให้คืนค่า 0
- ถ้า dp[i, m] ไม่ใช่ -1 ให้คืนค่า dp[i, m]
- ถ้า i – 1 + 2m>=ขนาดของอาร์เรย์ ให้คืนค่า arr[i]
- op :=inf
- สำหรับ x ในช่วง 1 ถึง 2 เมตร
- op :=นาทีของ op, แก้ (arr, i + x, สูงสุดของ x และ m, dp)
- dp[i, m] :=arr[i] – op
- ส่งคืน dp[i, m]
- วิธีการจริงจะเป็นเช่น −
- n :=ขนาดของอาร์เรย์ไพล์ สร้างหนึ่งอาร์เรย์ที่เรียกว่า arr ของขนาด n
- 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
