Leetcode1140和Leetcode1406同一类题,后缀和求和的思路参考大佬wzc1995的 代码
const int INF = 1e9, N =110;
class Solution {
public:
int n;
vector<int> sum;
int dp[N][N];
int dfs(int l, int m){
if (l>n) return 0;
if (dp[l][m] != -1) return dp[l][m];
for (int len = 1; len <=2*m; len++){
int r = l + len -1;
//max{[l,n]区间和-对手能获得的最大值}是当前能获得的最大值
dp[l][m] = max(dp[l][m], sum[l] - dfs(r+1, max(len, m)));
}
return dp[l][m];
}
int stoneGameII(vector<int>& piles) {
n = piles.size();
//后缀和
sum.resize(n+2, 0);
memset(dp, -1, sizeof dp);
for (int i = n; i>=1; i--)
sum[i] = piles[i-1] + sum[i+1];
return dfs(1, 1);
}
};