leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1406.cpp (614B)

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 };