Stone Game Greedy or DP?
This week, we have two stone games, one is for biweekly and one is in the weekly contest.
This kind of problem looks like a game theory problem. Usually, we can use greedy or DP to solve the problem. For this week’s two questions, one can be solved by using greedy and one can be solved by using DP.
1686. Stone Game VI
The intuition here is both Alice and Bob want to get more value, and at the same time, they want the other people to get less value. In order to achieve that, the optimal solution will be sorting a[i]+b[i] where a is values for Alice and b is values for Bob. a[i] + b[i] means the overall contribution of this stone. For example, if Alice take stone i, alice gets a[i] points, at the same time, bob lose b[i] points, so the total value for this stone is a[i] + b[i]. Generally speaking, we want we get more and at the same time we want the other side lose as much as possible. We have to consider those together.
class Solution {
public:
int stoneGameVI(vector<int>& a, vector<int>& b) {
const int n = a.size();
vector<pair<int, int>> values(n);
int A =0, B =0;
for (int i = 0; i < n; ++i) {
values[i] = {a[i]+b[i], i};
}
sort(values.rbegin(), values.rend());
for (int i = 0; i < n; ++i) {
auto idx = values[i].second;
if (i%2==0) {
A += a[idx];
} else {
B += b[idx];
}
}
if (A > B) return 1;
else if (A == B) return 0;
else return -1;
}
};1690. Stone Game VII
This is a classical problem can be solved by using DP.
Here is my ugly solution. Simulate the whole process by using a DFS way and memo the results if we have caculated before.
int dp[1001][1001];
int dp1[1001][1001];
class Solution {
public:
void helper(int i, int j, vector<int>& dq, bool turna, int sum) {
if (dp[i][j]!=-1) {
return;
}
int a, b;
if (j-i==1) {
if (turna){
if ( dq[i]< dq[j]){
a = dq[j];
b = 0;
}
else {
a = dq[i];
b = 0;
}
dp[i][j] = a;
dp1[i][j] = b;
return;
} else {
if ( dq[i]< dq[j]){
b = dq[j];
a = 0;
}
else {
b = dq[i];
a = 0;
}
dp[i][j] = a;
dp1[i][j] = b;
return;
}
} else {
int la=0, lb=0, ra =0, rb=0;
auto left = dq[i];
auto right = dq[j];
if (turna){
helper(i+1, j, dq, false, sum-left);
helper(i, j-1, dq,false, sum-right);
} else {
helper(i+1, j, dq, true, sum-left);
helper(i, j-1, dq, true, sum-right);
}
la = dp[i+1][j];
lb = dp1[i+1][j];
ra = dp[i][j-1];
rb = dp1[i][j-1];
if (turna) {
if (sum - left + la - lb > sum - right + ra - rb ) {
a = sum - left +la;
b = lb;
} else {
a = sum - right +ra;
b = rb;
}
} else {
if (la - (sum - left + lb) < ra-(sum- right + rb) ) {
a = la;
b = sum - left + lb;
} else {
a = ra;
b = sum - right + rb;
}
}
dp[i][j] = a;
dp1[i][j] = b;
}
}
int stoneGameVII(vector<int>& stones) {
memset (dp, -1, sizeof(dp));
int sum =0;
for (auto x:stones)sum+=x;
deque<int> dq(stones.begin(), stones.end());
int a=0, b=0;
int n = stones.size();
helper(0, n-1, stones, true, sum);
return dp[0][n-1]- dp1[0][n-1];
}
};TOP Down DP
It can be solved by using a TOP Down DP
int dp[1001][1001];
class Solution {
public:
int helper(int i, int j, vector<int>& stones, vector<int>& prefix) {
if (dp[i][j] != -1) return dp[i][j];
if (i == j) return dp[i][j] = 0;
int L = helper(i+1, j, stones, prefix);
int R = helper(i, j - 1, stones, prefix);
return dp[i][j] = max(prefix[j] - prefix[i] - L, prefix[j-1] - (i-1>=0?prefix[i-1]:0) - R);
}
int stoneGameVII(vector<int>& stones) {
memset(dp, -1, sizeof(dp));
const int n = stones.size();
vector<int> prefix(n);
prefix[0] = stones[0];
for (int i = 1; i < n; ++i) {
prefix[i] = prefix[i-1] + stones[i];
}
auto ret= helper(0, n-1, stones, prefix);
return ret;
}
};Bottom up DP
It can also be solved by bottom up DP
C++
int dp[1001][1001];
class Solution {
public:
int stoneGameVII(vector<int>& stones) {
memset(dp, -1, sizeof(dp));
const int n = stones.size();
vector<int> prefix(n+1);
for (int i = 0; i < n; ++i) {
prefix[i+1] = prefix[i] + stones[i];
}
for (int i = n-1; i >=0; --i){
for (int j = i; j < n; ++j) {
if (i == j) {
dp[i][j] = 0;
continue;
}
int L = (prefix[j+1] - prefix[i+1]) - dp[i+1][j];
int R = (prefix[j] - prefix[i]) - dp[i][j-1];
dp[i][j] = max(L, R);
}
}
return dp[0][n-1];
}
};Python code
class Solution:
def stoneGameVII(self, stones: List[int]) -> int:
n = len(stones)
dp = [[0 for _ in range(n)] for _ in range(n)]
prefix = [0]
for stone in stones:
prefix.append(prefix[-1] + stone)
for i in range(n-1, -1, -1):
for j in range(i, n):
if i==j: continue
L = prefix[j+1] -prefix[i+1] - dp[i+1][j]
R = prefix[j] -prefix[i] - dp[i][j-1]
dp[i][j] = max(L, R)
return dp[0][n-1]Thanks for reading.
