【題目敘述】https://leetcode.com/problems/stone-game/
【解題想法】參考類似題 TIOJ 1029 . A遊戲 【題解】
class Solution {
public:
bool stoneGame(vector<int>& piles) {
int n, s = 0, a[505][505];
n = piles.size();
for (int i = 2; i < n+2; i++){
a[i][i] = piles[i-2];
s += a[i][i];
for (int j = i-1; j >= 2; j--){
a[j][i] = max(a[j][j] + min(a[j+1][i-1], a[j+2][i]),
a[i][i] + min(a[j][i-2], a[j+1][i-1]));
}
}
if (a[2][n+1] > s - a[2][n+1]) return true;
else return false;
}
};