文章目錄
- 1. 題目
- 2. 解題
1. 題目
石子游戲中，愛麗絲和鮑勃輪流進行自己的回合，愛麗絲先開始 ，
有 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
提示：
n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/stone-game-vii
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
2. 解題
類似題目：
LeetCode 877. 石子游戲（DP）
LeetCode 1140. 石子游戲 II（DP）*
LeetCode 1406. 石子游戲 III（DP）
LeetCode 1563. 石子游戲 V（DP）
LeetCode 5447. 石子游戲 IV hard（博弈DP）
LeetCode 1025. 除數博弈（動態規劃）
LeetCode 5611. 石子游戲 VI（貪心）
- 前綴和預處理，方便后面快速獲取區間的和
dp[i][j]表示 剩下石頭為[i,j]時，先手可以獲得的最大分差
class Solution {
public:
int stoneGameVII(vector<int>& stones) {
int n = stones.size();
vector<int> sum(n+1);
for(int i = 1; i <= n; ++i)
sum[i] = sum[i-1] + stones[i-1];//前綴和
vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
for(int i = 1; i+1 <= n; ++i)
{ // 初始化情況，區間只剩2顆石頭的情況下，先手拿的最大分差
dp[i][i+1] = max(stones[i-1], stones[i]);
}
for(int len = 2; len <= n; ++len)
{ // 區間長度
for(int i = 1; i+len <= n; ++i)
{ // 左端點
int j = i+len; // 右端點
dp[i][j] = max(dp[i][j],
max(-dp[i+1][j]+sum[j]-sum[i],-dp[i][j-1]+sum[j-1]-sum[i-1]));
// 上一個人的分差取負，就是我的分差 + 我這次獲得的分數（前綴和獲取）
}
}
return dp[1][n];
}
};
364 ms 83.6 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/234337.html
標籤：其他
上一篇：總結與短期規劃
下一篇：Java人機猜拳思路及實作