Hai người Alex và Lee chơi game đá. Số đống chẵn, mỗi đống piles[i] viên. Lượt lượt lấy đống đầu hoặc cuối. Ai nhiều đá hơn thắng. Alex đi trước, cả hai chơi tối ưu. Kiểm tra Alex thắng không.
Ví dụ: [5,3,4,5] → true.
Giải pháp DP:
dp[i][j] = max điểm chênh lệch người chơi hiện tại có thể đạt trên đoạn i..j
pre[i] = tổng piles[0..i-1]
Với độ dài l=2..n:
dp[i][j] = max(piles[j] + (pre[j]-pre[i]) - dp[i][j-1], piles[i] + (pre[i+2]-pre[j]) + dp[i+1][j])Alex thắng nếu dp[0][n-1] > tổng - dp[0][n-1]
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: bool stoneGame(vector<int>& piles) { int n = piles.size(); vector<vector<int>> dp(n, vector<int>(n)); vector<int> pre(n+1); for(int i=0;i<n;i++) pre[i+1]=pre[i]+piles[i]; for(int l=2;l<=n;l++){ for(int i=0,j=l-1;j<n;i++,j++){ dp[i][j]=max(piles[j]+pre[j]-pre[i]-dp[i][j-1], piles[i]+pre[i+2]-pre[j]+dp[i+1][j]); } } return dp[0][n-1] > dp[0][n-1] - pre[n]; } }; int main(){ vector<int> v={5,3,4,5}; Solution ob; cout << ob.stoneGame(v); }Đầu vào
[5,3,4,5]
Đầu ra
1