Stone Game Greedy or 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.

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]

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi