Stone Game Greedy or DP?

1686. Stone Game VI

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

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

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

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