[数据结构与算法]1690. 石子游戏 VII-动态规划法

1690. 石子游戏 VII

石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。

有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。

鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。

给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。

示例 1：

输入：stones = [5,3,1,4,2]
输出：6
解释：

• 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。
• 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。
• 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。
• 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
• 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
  得分的差值 18 - 12 = 6 。

示例 2：

输入：stones = [7,90,5,1,100,10,10,2]
输出：122

这题动态规划的核心思想就是，我们由小区间到大区间进行计算，每次从两个数据的小区间扩大到大区间，并存储结果，最后求出结果

int stoneGameVII(int* stones, int stonesSize){
    int preSum[stonesSize + 1];
    preSum[0] = 0;
    //前缀和
    for(int i = 0; i < stonesSize; i++){
        preSum[i + 1] = preSum[i] + stones[i];
        }
    //区间[i, j]的和等于preSum[j + 1] - preSum[i]

    
    //j == i + 1时，由于只有两个元素，为了使差值更大，移除小的数
    //j > i + 1时，考虑移除元素后对手下一步能拉出的最大差距
    int dp[stonesSize][stonesSize];
    memset(dp, 0, sizeof(dp));
    for(int i = stonesSize - 2; i >= 0; i--){
        for(int j = i + 1; j < stonesSize; j++){
            if(j == i + 1){
                dp[i][j] = fmax(stones[i], stones[j]);
                }
            else{
                int l = preSum[j + 1] - preSum[i + 1];  //移除左侧石头后区间[i + 1, j]的和
                int r = preSum[j] - preSum[i];  //移除右侧石头后区间[i, j - 1]的和
                dp[i][j] = fmax(l - dp[i + 1][j], r - dp[i][j - 1]);
                }
            }
        }
    return dp[0][stonesSize - 1];
}