leetcode

0 class Solution {

1 public:

2 string stoneGameIII(const vector<int> &stoneValue) {

3 int n = stoneValue.size();

4 vector<int> sum(n + 1, 0), dp(n + 1, 0);

5

6 for (int i = n - 1; i >= 0; i--)

7 sum[i] = sum[i + 1] + stoneValue[i];

8

9 for (int i = n - 1; i >= 0; i--) {

10 dp[i] = stoneValue[i] + sum[i + 1] - dp[i + 1];

11 for (int k = i + 1; k < i + 3 && k < n; k++) {

12 dp[i] = max(dp[i], sum[i] - dp[k + 1]);

13 }

14 }

15 dp[0] = dp[0] * 2 - sum[0];

16 return dp[0] == 0 ? "Tie" : (dp[0] > 0 ? "Alice" : "Bob");

17 }

18 };