2D DP

Problem

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);
}
};

Data Scientist/MLE/SWE @takemobi