題目
分析
題意還是比較好理解的食棕，每次將石子分成兩大堆渗磅，拋棄總和大的那一堆，留下少的一堆并且總分數中加上少的一堆的和按灶，直至只剩下一個石頭症革，游戲結束。而題目給的數據規(guī)模在500鸯旁，那么算法的復雜度要在O(n2)以內噪矛。
首先考慮一下暴力解法。當石子大于一塊時铺罢，遍歷每一個可能的分割位置艇挨，分別計算兩邊的和，留下少的一堆并在答案中加上少的那堆的和韭赘，比較所有的可能雷袋，找到最大的分數，其中計算部分和可以使用前綴和數組預處理來減少時間復雜度。而在暴力解法中楷怒，會出現很多區(qū)間重復計算的問題蛋勺，動態(tài)規(guī)劃顯然是一個好的處理方式。
區(qū)間動態(tài)規(guī)劃
狀態(tài)定義
由于是區(qū)間上的動態(tài)規(guī)劃問題鸠删，定義時抱完，可以使用二維數組dp[i][j]，枚舉所有區(qū)間刃泡，也就是 i 表示區(qū)間頭巧娱，j 表示區(qū)間尾，根據題意烘贴，可以想到dp數組的定義：dp[i][j]表示在區(qū)間(i, j)上禁添，Alice能獲得的最大分數，由此可以得到基礎狀態(tài)：
- 對于長度為一的區(qū)間桨踪，只剩一塊石子老翘，游戲結束，即
dp[i][i] = 0
狀態(tài)轉移
由于要找到所有的分割方法中的最優(yōu)方法锻离，所以狀態(tài)轉移時肯定需要遍歷每個分割位置取最大值铺峭。然后對于每個分割位置，根據題意汽纠，取和小的那一堆卫键，然后對小的那堆繼續(xù)分割，小的那一堆也就相當于sum[j] - sum[i]虱朵，而小的那堆繼續(xù)分割的值在之前已經計算過莉炉，為dp[i][j]，所以可以得到：
if (sum[k + 1] - sum[i] > sum[j + 1] - sum[k + 1]) {
dp[i][j] = Math.max(dp[i][j], sum[j + 1] - sum[k + 1] + dp[k + 1][j]);
} else if (sum[k + 1] - sum[i] < sum[j + 1] - sum[k + 1]) {
dp[i][j] = Math.max(dp[i][j], sum[k + 1] - sum[i] + dp[i][k]);
}
這里的 i 表示區(qū)間頭碴犬，j 表示區(qū)間尾呢袱，k 表示分割位置，sum 表示前綴和數組翅敌，下標要慎重考慮。
除了這樣兩種情況惕蹄，還有兩堆相等的情況蚯涮，兩堆相等并不能給出明確的選擇給出哪個更好，所以應該計算左堆和右堆卖陵，取其中的最大值：
dp[i][j] = Math.max(dp[i][j],
Math.max(sum[j + 1] - sum[k + 1] + dp[k + 1][j], sum[k + 1] - sum[i] + dp[i][k]));
這里每次取dp[i][j]和另一個值比較是為了遍歷分割位置 k 時取到所以結果中的最大值遭顶。
完整代碼
有了狀態(tài)定義、初始狀態(tài)及狀態(tài)轉移泪蔫，就可以寫出DP代碼了棒旗，通常情況的區(qū)間DP問題采用先循環(huán)遍歷區(qū)間長度，再循環(huán)遍歷區(qū)間頭來遍歷所有可能并且保證后邊用到的值在先前已經得到。
class Solution {
private int[][] dp;
public int stoneGameV(int[] a) {
int n = a.length;
// 前綴和
int[] sum = new int[a.length + 1];
for (int i = 0; i < a.length; i++) {
sum[i + 1] = sum[i] + a[i];
}
dp = new int[n][n];
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
if (sum[k + 1] - sum[i] > sum[j + 1] - sum[k + 1]) {
dp[i][j] = Math.max(dp[i][j], sum[j + 1] - sum[k + 1] + dp[k + 1][j]);
} else if (sum[k + 1] - sum[i] < sum[j + 1] - sum[k + 1]) {
dp[i][j] = Math.max(dp[i][j], sum[k + 1] - sum[i] + dp[i][k]);
} else {
dp[i][j] = Math.max(dp[i][j],
Math.max(sum[j + 1] - sum[k + 1] + dp[k + 1][j], sum[k + 1] - sum[i] + dp[i][k]));
}
}
}
}
return dp[0][n - 1];
}
}
用時在500ms左右铣揉，也可以采用記憶化遞歸來處理饶深，時間可以達到70ms左右，這里我也不太懂原因是什么逛拱，理論上循環(huán)計算要比遞歸調用用時短一些敌厘，可力扣上好多這樣的題都是記憶化遞歸快，不是很懂他運行的機制朽合，改寫成遞歸還是比較簡單的俱两，只要把k部分的循環(huán)寫到遞歸里即可，我這里就不在給出代碼了曹步。
總結
DP問題可真是老大難宪彩，各種各樣的形式，思想差不多但是方法不同的解法讲婚，dp數組的定義尿孔，沒有一樣很容易掌握，但還是需要去學習啊磺樱。區(qū)間DP也是一個比較常見的DP問題類型纳猫，一點點努力，一點點進步~
文章如果有不正確的地方還請指出竹捉，感恩相遇~~
