leetcode

commit 12af5344843e003e9aaf70ee327e8295ed670055
parent 06cab644c81aaeee594becccac30c52fd4a79758
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 27 May 2023 13:03:49 +0200

Daily Problem

Diffstat:
A
Problems/1406.cpp
 | 
18
++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 19 insertions(+), 0 deletions(-)
diff --git a/Problems/1406.cpp b/Problems/1406.cpp
@@ -0,0 +1,18 @@
+class Solution {
+public:
+  string stoneGameIII(const vector<int> &stoneValue) {
+    int n = stoneValue.size();
+    vector<int> sum(n + 1, 0), dp(n + 1, 0);
+
+    for (int i = n - 1; i >= 0; i--) sum[i] = sum[i + 1] + stoneValue[i];
+
+    for (int i = n - 1; i >= 0; i--) {
+      dp[i] = stoneValue[i] + sum[i + 1] - dp[i + 1];
+      for (int k = i + 1; k < i + 3 && k < n; k++) {
+        dp[i] = max(dp[i], sum[i] - dp[k + 1]);
+      }
+    }
+    dp[0] = dp[0] * 2 - sum[0];
+    return dp[0] == 0 ? "Tie" : (dp[0] > 0 ? "Alice" : "Bob");
+  }
+};
diff --git a/README.md b/README.md
@@ -442,6 +442,7 @@ for solving problems.
 |  1379  |    Easy    | [Find a Corresponding Node of a Binary Tree in a Clone of That Tree](Problems/1379.cpp)          |
 |  1382  |   Medium   | [Balance a Binary Search Tree](Problems/1382.cpp)                                                |
 |  1402  |    Hard    | [Reducing Dishes](Problems/1402.cpp)                                                             |
+|  1406  |    Hard    | [Stone Game III](Problems/1406.cpp)                                                              |
 |  1416  |    Hard    | [Restore The Array](Problems/1416.cpp)                                                           |
 |  1425  |    Hard    | [Constrained Subsequence Sum](Problems/1425.cpp)                                                 |
 |  1431  |    Easy    | [Kids With the Greatest Number of Candies](Problems/1431.cpp)                                    |