leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1406.cpp (614B)

      1 class Solution {
      2   public:
      3     string stoneGameIII(const vector<int> &stoneValue) {
      4         int n = stoneValue.size();
      5         vector<int> sum(n + 1, 0), dp(n + 1, 0);
      6 
      7         for (int i = n - 1; i >= 0; i--)
      8             sum[i] = sum[i + 1] + stoneValue[i];
      9 
     10         for (int i = n - 1; i >= 0; i--) {
     11             dp[i] = stoneValue[i] + sum[i + 1] - dp[i + 1];
     12             for (int k = i + 1; k < i + 3 && k < n; k++) {
     13                 dp[i] = max(dp[i], sum[i] - dp[k + 1]);
     14             }
     15         }
     16         dp[0] = dp[0] * 2 - sum[0];
     17         return dp[0] == 0 ? "Tie" : (dp[0] > 0 ? "Alice" : "Bob");
     18     }
     19 };