# 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]`

--

--

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.