leetcode

commit 06cab644c81aaeee594becccac30c52fd4a79758
parent 960f0123c61a6781c3a413ff7816f7ccd8ecf0c4
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 26 May 2023 16:50:14 +0200

Daily Problem

Diffstat:
A
Problems/1140.cpp
 | 
23
+++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 24 insertions(+), 0 deletions(-)
diff --git a/Problems/1140.cpp b/Problems/1140.cpp
@@ -0,0 +1,23 @@
+class Solution {
+  int dp[10001][101];
+
+public:
+  Solution() { memset(dp, 0, sizeof(dp)); }
+
+  int stoneGameII(const vector<int> &piles) {
+    int n = piles.size();
+    vector<int> sum(n + 1, 0);
+    for (int i = n - 1; i >= 0; i--) {
+      dp[i][n] = sum[i] = sum[i + 1] + piles[i];
+    }
+
+    for (int i = n - 1; i >= 0; i--) {
+      for (int j = n - 1; j >= 1; j--) {
+        for (int X = 1; X <= 2 * j && i + X <= n; X++) {
+          dp[i][j] = max(dp[i][j], sum[i] - dp[i + X][max(j, X)]);
+        }
+      }
+    }
+    return dp[0][1];
+  }
+};
diff --git a/README.md b/README.md
@@ -413,6 +413,7 @@ for solving problems.
 |  1099  |    Easy    | [Replace Elements with Greatest Element on Right Side](Problems/1099.cpp)                        |
 |  1129  |   Medium   | [Shortest Path with Alternating Colors](Problems/1129.cpp)                                       |
 |  1137  |    Easy    | [N-th Tribonacci Number](Problems/1137.cpp)                                                      |
+|  1140  |   Medium   | [Stone Game II](Problems/1140.cpp)                                  |
 |  1143  |   Medium   | [Longest Common Subsequence](Problems/1143.cpp)                                                  |
 |  1162  |   Medium   | [As Far from Land as Possible](Problems/1162.cpp)                                                |
 |  1202  |   Medium   | [Smallest String With Swaps](Problems/1202.cpp)                                                  |