leetcode 动态规划

1140. Stone Game II

题意比较难懂。

accumulate带有三个形参：头两个形参指定要累加的元素范围，第三个形参则是累加的初值。

int arr[]={10,20,30,40,50};  
vector<int> va(&arr[0],&arr[5]);  
int sum=accumulate(va.begin(),va.end(),0);  //sum = 150 

解1：

class Solution {
public:
    
    int maximum(vector<int>& piles, int start, int M, int total) {

        if (start >= piles.size()) return 0;

        if (cache[start][M] != -1) {
            return cache[start][M];
        }
        
        int result = INT_MIN;
        
        for (int X = 1, sum = 0; X <= 2 * M && X + start <= piles.size(); X++) {
            sum += piles[start + X - 1];
            //递归计算当前玩家可以使用的所有下线石头数量。从（total）中减去maximum()。
            // 我们计算的是从下一回合中对方玩家获得的最大石头数。当前玩家的最大得分=（total）- 其他玩家的最大得分。
            result = max(result, total - maximum(piles, start + X, max(M, X), total - sum));
        }
        return cache[start][M] = result;
    }
    
    int stoneGameII(vector<int>& piles) {
        cache = vector<vector<int>>(piles.size(), vector<int>(piles.size(), -1));
        return maximum(piles, 0, 1, accumulate(piles.begin(), piles.end(), 0));
    }
private:
    vector<vector<int>> cache;
};            

解2：

int memo[101][32] = {};
int dfs(vector<int>& dp, int x, int m, int res = INT_MIN) {
  // 如果当前数组的石头能全都要，那就全都要。
  if (x + m * 2 >= dp.size()) return dp[dp.size() - 1] - dp[x - 1];
  // 如果对应当前x和m的数量已经计算过了，直接返回，避免重复计算。
  if (memo[x][m]) return memo[x][m];
  // x的可选范围x ~ x+2m，至多当前x之后2m范围的石头。
  for (int i = x; i < x + m * 2 && i < dp.size(); ++i)
    res = max(res, dp[i] - (x == 0 ? 0 : dp[x - 1]) - dfs(dp, i + 1, max(m, i - x + 1)));
  return memo[x][m] = res;
}
int stoneGameII(vector<int>& ps) {
  partial_sum(begin(ps), end(ps), begin(ps));
  return (ps[ps.size() - 1] + dfs(ps, 0, 1)) / 2;
}