Create stone-game.cpp

kamyu104 · web-flow · commit 573c022aefb1 · 2018-07-29T15:05:48.000+08:00
diff --git a/C++/stone-game.cpp b/C++/stone-game.cpp
@@ -0,0 +1,23 @@
+// Time:  O(n^2)
+// Space: O(n)
+
+// The solution is the same as https://leetcode.com/problems/predict-the-winner/description/
+class Solution {
+public:
+    bool stoneGame(vector<int>& piles) {
+        if (piles.size() % 2 == 0 || piles.size() == 1) {
+            return true;
+        }
+
+        vector<int> dp(piles.size());
+        for (int i = piles.size() - 1; i >= 0; --i) {
+            dp[i] = piles[i];
+            for (int j = i + 1; j < piles.size(); ++j) {
+                dp[j] = max(piles[i] - dp[j], piles[j] - dp[j - 1]);
+            }
+        }
+        
+        return dp.back() >= 0;
+    }
+};
+
