2D DP

1563. Stone Game V

Problem

1536 Stone Game V

This is the last question of this weekly contest. We can solve it by using the 2D DP.

Memo[i][j] means the maximum score Alice can get if the array if from stones[i: j+1].

Solution

int memo[501][501];
class Solution {
public:
    int dp(vector<int>& stones,vector<int>& cusum, int i, int j) {
        if (i == j) return memo[i][j] = 0;
        if (memo[i][j] != -1) return memo[i][j];
        int this_ret = INT_MIN;
        for (int k = i; k < j; ++k) {
            auto li = i, lj = k, ri = k + 1 , rj = j;
            auto sumL =cusum[lj+1] - cusum[li],   sumR = cusum[rj+1] - cusum[ri];
            if (sumL > sumR) this_ret = max(this_ret, sumR + dp(stones, cusum, ri, rj));
            else if  (sumL < sumR) this_ret = max(this_ret, sumL + dp(stones, cusum, li, lj));
            else {
                auto left = dp(stones, cusum, li, lj);
                auto right = dp(stones, cusum, ri, rj);
                if (sumL + left > sumR + right ) {
                    this_ret = max(this_ret, sumL + left);
                }
                else {
                     this_ret = max(this_ret, sumR + right);
                }
            }
            
        }
        return memo[i][j] = this_ret;
    }
    int stoneGameV(vector<int>& stones) {
        memset(memo, -1, sizeof(memo));
        const int N = stones.size();
        vector<int> cusum(N+1, 0);
        for (int i = 0; i < N; ++i) {
            cusum[i+1] = cusum[i] + stones[i];
        }
        return dp(stones, cusum, 0, N-1);
    }
};